LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)

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

截止到目前我已经写了 600多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)

LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)

LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)
LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)

public boolean wordBreak(String s, List<String> dict) {
    boolean[] dp = new boolean[s.length() + 1];
    for (int i = 1; i <= s.length(); i++) {
        //枚举k的值
        for (int k = 0; k <= i; k++) {
            //如果往前截取全部字符串,我们直接判断子串[0,i-1]
            //是否存在于字典wordDict中即可
            if (k == i) {
                if (dict.contains(s.substring(0, i))) {
                    dp[i] = true;
                    continue;
                }
            }
            //递推公式
            dp[i] = dp[i - k] && dict.contains(s.substring(i - k, i));
            //如果dp[i]为true,说明前i个字符串结果拆解可以让他的所有子串
            //都存在于字典wordDict中,直接终止内层循环,不用再计算dp[i]了。
            if (dp[i]) {
                break;
            }
        }
    }
    return dp[s.length()];
}

上面代码有一个判断,就是截取的是前面全部字符串的时候要单独判断,其实当截取全部的时候我们只需要判断这个字符串是否存在于字典wordDict中即可,可以让dp[0]truedp[0]表示的是空字符串。这样代码会简洁很多,我们来看下

public boolean wordBreak(String s, List<String> dict) {
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;//边界条件
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = dp[j] && dict.contains(s.substring(j, i));
            if (dp[i]) {
                break;
            }
        }
    }
    return dp[s.length()];
}

这个和第一种写法不太一样,这个每次截取的方式如下图所示。
LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)
LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)
LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)
LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)
每次截取一个子串,判断他是否存在于字典中,如果不存在于字典中,继续截取更长的子串……如果存在于字典中,然后递归拆分剩下的子串,这是一个递归的过程。上面的执行过程我们可以把它看做是一棵n叉树的DFS遍历,所以大致代码我们可以列出来

public boolean wordBreak(String s, List<String> wordDict) {
    return dfs(s, wordDict);
}

public boolean dfs(String s, List<String> wordDict) {
    if (最终条件,都截取完了,直接返回true)
    return true;
    //开始拆分字符串s
    for (int i = 开始截取的位置; i <= s.length(); i++) {
        //如果截取的子串不在字典中,继续截取更大的子串
        if (!wordDict.contains(截取子串))
            continue;
        //如果截取的子串在字典中,继续剩下的拆分,如果剩下的可以拆分成
        //在字典中出现的单词,直接返回true,如果不能则继续
        //截取更大的子串判断
        if (dfs(s, wordDict))
            return true;
    }
    //如果都不能正确拆分,直接返回false
    return false;
}

上面代码中因为递归必须要有终止条件,通过上面的图我们可以发现,终止条件就是把字符串s中的所有字符都遍历完了,这个时候说明字符串s可以拆分成一些子串,并且这些子串都存在于字典中。我们来看个图

LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)
因为是拆分,所以字符串截取的时候不能有重叠,那么[开始截取的位置]实际上就是上次截取位置的下一个,来看下代码。

public boolean wordBreak(String s, List<String> wordDict) {
    return dfs(s, wordDict, 0);
}

//start表示的是从字符串s的哪个位置开始
public boolean dfs(String s, List<String> wordDict, int start) {
    //字符串中的所有字符都遍历完了,也就是到叶子节点了,说明字符串s可以拆分成
    //在字典中出现的单词,直接返回true
    if (start == s.length())
        return true;
    //开始拆分字符串s,
    for (int i = start + 1; i <= s.length(); i++) {
        //如果截取的子串不在字典中,继续截取更大的子串
        if (!wordDict.contains(s.substring(start, i)))
            continue;
        //如果截取的子串在字典中,继续剩下的拆分,如果剩下的可以拆分成
        //在字典中出现的单词,直接返回true,如果不能则继续
        //截取更大的子串判断
        if (dfs(s, wordDict, i))
            return true;
    }
    return false;
}

实际上上面代码运行效率很差,这是因为如果字符串s比较长的话,这里会包含大量的重复计算,我们还用上面的图来看下

LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)
我们看到红色的就是重复计算,这里因为字符串比较短,不是很明显,当字符串比较长的时候,这里的重复计算非常多。我们可以使用一个变量,来记录计算过的位置,如果之前判断过,就不在重复判断,直接跳过即可,代码如下

public boolean wordBreak(String s, List<String> wordDict) {
    return dfs(s, wordDict, new HashSet<>(), 0);
}

//start表示的是从字符串s的哪个位置开始
public boolean dfs(String s, List<String> wordDict, Set<Integer> indexSet, int start) {
    //字符串都拆分完了,返回true
    if (start == s.length())
        return true;
    for (int i = start + 1; i <= s.length(); i++) {
        //如果已经判断过了,就直接跳过,防止重复判断
        if (indexSet.contains(i))
            continue;
        //截取子串,判断是否是在字典中
        if (wordDict.contains(s.substring(start, i))) {
            if (dfs(s, wordDict, indexSet, i))
                return true;
            //标记为已判断过
            indexSet.add(i);
        }
    }
    return false;
}

LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)
LeetCode 139. 单词拆分(动态规划,DFS和BFS解决)
BFS一般不需要递归,只需要使用一个队列记录每一层需要记录的值即可。BFS中在截取的时候,如果截取的子串存在于字典中,我们就要记录截取的位置,到下一层的时候就从这个位置的下一个继续截取,来看下代码。

public boolean wordBreak(String s, List<String> wordDict) {
    //这里为了提高效率,把list转化为set,因为set的查找效率要比list高
    Set<String> setDict = new HashSet<>(wordDict);
    //记录当前层开始遍历字符串s的位置
    Queue<Integer> queue = new LinkedList<>();
    queue.add(0);
    int length = s.length();
    while (!queue.isEmpty()) {
        int index = queue.poll();
        //如果字符串到遍历完了,自己返回true
        if (index == length)
            return true;
        for (int i = index + 1; i <= length; i++) {
            if (setDict.contains(s.substring(index, i))) {
                queue.add(i);
            }
        }
    }
    return false;
}

这种也会出现重复计算的情况,所以这里我们也可以使用一个变量来记录下。文章来源地址https://www.toymoban.com/news/detail-401996.html

public boolean wordBreak(String s, List<String> wordDict) {
    //这里为了提高效率,把list转化为set,因为set的查找效率要比list高
    Set<String> setDict = new HashSet<>(wordDict);
    //记录当前层开始遍历字符串s的位置
    Queue<Integer> queue = new LinkedList<>();
    queue.add(0);
    int length = s.length();
    //记录访问过的位置,减少重复判断
    boolean[] visited = new boolean[length];
    while (!queue.isEmpty()) {
        int index = queue.poll();
        //如果字符串都遍历完了,直接返回true
        if (index == length)
            return true;
        //如果被访问过,则跳过
        if (visited[index])
            continue;
        //标记为访问过
        visited[index] = true;
        for (int i = index + 1; i <= length; i++) {
            if (setDict.contains(s.substring(index, i))) {
                queue.add(i);
            }
        }
    }
    return false;
}

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

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

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

相关文章

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

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

    2023年04月20日
    浏览(61)
  • 解决背包衍生题目:单词拆分和分割等和子集--动态规划方式深度呈现

    目录 139. 单词拆分 解题思路 代码实现 416. 分割等和子集 二维动态规划 状态压缩(一维) 问题拓展 背包九讲知识总结 相关问题 题目描述 给你一个字符串  s  和一个字符串列表  wordDict  作为字典。请你判断是否可以利用字典中出现的单词拼接出  s  。 注意: 不要求字典中

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

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

    2024年01月22日
    浏览(42)
  • 【学会动态规划】单词拆分(24)

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

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

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

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

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

    2024年02月03日
    浏览(38)
  • 力扣 | 139. 单词拆分

    主要是要注意组合的顺序是任意的!所以就要先选择目标字串,再选择wordDict

    2024年01月22日
    浏览(40)
  • 力扣 -- 139. 单词拆分

     题目链接:139. 单词拆分 - 力扣(LeetCode) 下面是用动态规划的思想解决这道题的过程,相信各位小伙伴都能看懂并且掌握这道经典的动规题目滴。   以上就是用动态规划的思想分析这道题目的整个过程啦,你学会了吗?如果以上题解对你有所帮助,那么就点亮一下小心心

    2024年02月14日
    浏览(47)
  • 算法-图BFS/DFS-单词接龙

    https://leetcode-cn.com/problems/number-of-islands 给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则: 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明: 如果不存在这样的转换序列,返回

    2024年02月10日
    浏览(43)
  • leetcode 343.整数拆分 198.打家劫舍(动态规划)

       OJ链接 :leetcode 343.整数拆分 代码:  OJ链接 :198.打家劫舍    代码:

    2024年02月05日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包