力扣:139. 单词拆分

这篇具有很好参考价值的文章主要介绍了力扣:139. 单词拆分。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划:

1.先声明dp数组的含义为下标i表示的是在s变量中i前面的字符串是否在wordDict变量中存在,初始化dp【0】来进行后面dp数组的递推。同时要判断截取的值是否在wirdDict中是否存在,还要判断dp【j】的下标的j前面的字符串是否也在wirdDict中,如果都符合条件就给dp【i】赋值true。文章来源地址https://www.toymoban.com/news/detail-828358.html

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //dp数组的下标i表示的时在s变量中i前面的字符串是否在wordDict变量中存在
            boolean[] dp=new boolean[s.length()+1];
            //初始化dp【0】来进行后面的dp数组递推
            dp[0]=true;
            for(int i=1;i<=s.length();i++){
                for(int j=0;j<i;j++){
                    //截取s变量中j-i的值来进行判断是否在wordDict中存在
                    String st=s.substring(j, i);
     //判断条件截取的值在wordDict中,同时j之前的值都在wordDict中,就给dp【i】赋值为true
                    if(wordDict.contains(st)&&dp[j]==true){
                        dp[i]=true;
                    }
                }
            }
            //放回在s中最后一个下标的dp数组值
            return dp[s.length()];
    }
}

到了这里,关于力扣:139. 单词拆分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣:139. 单词拆分

    动态规划: 1.先声明dp数组的含义为下标i表示的是在s变量中i前面的字符串是否在wordDict变量中存在,初始化dp【0】来进行后面dp数组的递推。同时要判断截取的值是否在wirdDict中是否存在,还要判断dp【j】的下标的j前面的字符串是否也在wirdDict中,如果都符合条件就给dp【i】

    2024年02月20日
    浏览(37)
  • 力扣 139. 单词拆分

    给你一个字符串 s 和一个字符串列表 word_dict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意 :不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 通过 回溯法 进行 暴力 求解,时间复杂度 O ( n × 2 n ) O(n times 2^n) O ( n × 2 n ) ,空间

    2024年02月03日
    浏览(34)
  • leetcode 动态规划(单词拆分)

    139.单词拆分 力扣题目链接(opens new window) 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: 输入: s = “leetcode”

    2024年02月22日
    浏览(40)
  • Leetcode 139.单词拆分

    OJ链接 :139.单词拆分  代码:    

    2024年02月04日
    浏览(39)
  • 【LeetCode动态规划#10】完全背包问题实战,其三(单词拆分,涉及集合处理字符串)

    力扣题目链接(opens new window) 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: 输入: s = \\\"leetcode\\\", wordDict = [\\\"lee

    2023年04月20日
    浏览(58)
  • 【学会动态规划】单词拆分(24)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:139. 单词拆分 - 力扣(LeetCo

    2024年02月12日
    浏览(37)
  • 动态规划篇-06:单词拆分

    老样子,还是先尝试找出状态转移方程 对问题进行分解,尝试从子问题入手解决。 这也是前文提到过的 “分解问题” 的思想  对于输入的字符串 s,如果我能够从单词列表 wordDict 中找到一个单词匹配 s 的前缀 s[0..k],那么只要我能拼出 s[k+1..],就一定能拼出整个 s。换句话

    2024年01月22日
    浏览(40)
  • LeetCode算法题解(动态规划)|LeetCode343. 整数拆分、LeetCode96. 不同的二叉搜索树

    题目链接:343. 整数拆分 题目描述: 给定一个正整数  n  ,将其拆分为  k  个  正整数  的和(  k = 2  ),并使这些整数的乘积最大化。 返回  你可以获得的最大乘积  。 示例 1: 示例 2: 提示: 2 = n = 58 算法分析: 定义dp数组及下标含义: dp[i]表述正整数i拆分成k个正整数

    2024年02月04日
    浏览(39)
  • 【力扣】343. 整数拆分 <动态规划、数学>

    给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k = 2 ),并使这些整数的乘积最大化。返回可以获得的最大乘积 。 示例 1: 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 提示: 2 = n = 58 动态规划 确定 dp 数组以及下

    2024年02月09日
    浏览(42)
  • 整数拆分(力扣)动态规划 JAVA

    给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k = 2 ),并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 提示: 2 = n = 58 里程碑意义 解题思路:

    2024年02月17日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包