574，DFS和BFS解单词拆分

Original 博哥数据结构和算法 2022-05-01

You will never age for me, nor fade, nor die.

你于我而言，无岁月之流失，无花容之褪色，无人生之离别。

问题描述

给定一个非空字符串s和一个包含非空单词的列表wordDict，判定s是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入:
s = "leetcode",
wordDict = ["leet", "code"]

输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入:
s = "applepenapple",
wordDict = ["apple", "pen"]

输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。

示例 3：

输入:
s = "catsandog",
wordDict = ["cats", "dog", "sand", "and", "cat"]

输出: false

DFS解决

前面刚讲过这题，使用的是动态规划，具体可以看下《573，动态规划解单词拆分》，今天我们分别使用DFS和BFS来解决这道题。

这题要求的是把字符串拆分，并且判断拆分的子串是否都存在于字典中，那么字符串怎么拆分呢，我们举个例子来看下，比如字符串[abcd]，我们可以拆分为

[a,b,c,d]

[a,b,cd]

[a,bc,d]

[a,bcd]

[ab,c,d]

[ab,cd]

[abc,d]

[abcd]

具体来看下图

每次截取一个子串，判断他是否存在于字典中，如果不存在于字典中，继续截取更长的子串……如果存在于字典中，然后递归拆分剩下的子串，这是一个递归的过程。上面的执行过程我们可以把它看做是一棵n叉树的DFS遍历，所以大致代码我们可以列出来

 1public boolean wordBreak(String s, List<String> wordDict) {
 2    return dfs(s, wordDict);
 3}
 4
 5public boolean dfs(String s, List<String> wordDict) {
 6    if (最终条件，都截取完了，直接返回true)
 7    return true;
 8    //开始拆分字符串s
 9    for (int i = 开始截取的位置; i <= s.length(); i++) {
10        //如果截取的子串不在字典中，继续截取更大的子串
11        if (!wordDict.contains(截取子串))
12            continue;
13        //如果截取的子串在字典中，继续剩下的拆分，如果剩下的可以拆分成
14        //在字典中出现的单词，直接返回true，如果不能则继续
15        //截取更大的子串判断
16        if (dfs(s, wordDict))
17            return true;
18    }
19    //如果都不能正确拆分，直接返回false
20    return false;
21}

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

因为是拆分，所以字符串截取的时候不能有重叠，那么[开始截取的位置]实际上就是上次截取位置的下一个，来看下代码。

 1public boolean wordBreak(String s, List<String> wordDict) {
 2    return dfs(s, wordDict, 0);
 3}
 4
 5//start表示的是从字符串s的哪个位置开始
 6public boolean dfs(String s, List<String> wordDict, int start) {
 7    //字符串中的所有字符都遍历完了，也就是到叶子节点了，说明字符串s可以拆分成
 8    //在字典中出现的单词，直接返回true
 9    if (start == s.length())
10        return true;
11    //开始拆分字符串s，
12    for (int i = start + 1; i <= s.length(); i++) {
13        //如果截取的子串不在字典中，继续截取更大的子串
14        if (!wordDict.contains(s.substring(start, i)))
15            continue;
16        //如果截取的子串在字典中，继续剩下的拆分，如果剩下的可以拆分成
17        //在字典中出现的单词，直接返回true，如果不能则继续
18        //截取更大的子串判断
19        if (dfs(s, wordDict, i))
20            return true;
21    }
22    return false;
23}

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

我们看到红色的就是重复计算，这里因为字符串比较短，不是很明显，当字符串比较长的时候，这里的重复计算非常多。我们可以使用一个变量，来记录计算过的位置，如果之前判断过，就不在重复判断，直接跳过即可，代码如下

 1public boolean wordBreak(String s, List<String> wordDict) {
 2    return dfs(s, wordDict, new HashSet<>(), 0);
 3}
 4
 5//start表示的是从字符串s的哪个位置开始
 6public boolean dfs(String s, List<String> wordDict, Set<Integer> indexSet, int start) {
 7    //字符串都拆分完了，返回true
 8    if (start == s.length())
 9        return true;
10    for (int i = start + 1; i <= s.length(); i++) {
11        //如果已经判断过了，就直接跳过，防止重复判断
12        if (indexSet.contains(i))
13            continue;
14        //截取子串，判断是否是在字典中
15        if (wordDict.contains(s.substring(start, i))) {
16            if (dfs(s, wordDict, indexSet, i))
17                return true;
18            //标记为已判断过
19            indexSet.add(i);
20        }
21    }
22    return false;
23}

BFS解决

这题除了DFS以外，还可以使用BFS，BFS就是一层一层的遍历，如下图所示

BFS一般不需要递归，只需要使用一个队列记录每一层需要记录的值即可。BFS中在截取的时候，如果截取的子串存在于字典中，我们就要记录截取的位置，到下一层的时候就从这个位置的下一个继续截取，来看下代码。

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

这种也会出现重复计算的情况，所以这里我们也可以使用一个变量来记录下。

 1public boolean wordBreak(String s, List<String> wordDict) {
 2    //这里为了提高效率，把list转化为set，因为set的查找效率要比list高
 3    Set<String> setDict = new HashSet<>(wordDict);
 4    //记录当前层开始遍历字符串s的位置
 5    Queue<Integer> queue = new LinkedList<>();
 6    queue.add(0);
 7    int length = s.length();
 8    //记录访问过的位置，减少重复判断
 9    boolean[] visited = new boolean[length];
10    while (!queue.isEmpty()) {
11        int index = queue.poll();
12        //如果字符串都遍历完了，直接返回true
13        if (index == length)
14            return true;
15        //如果被访问过，则跳过
16        if (visited[index])
17            continue;
18        //标记为访问过
19        visited[index] = true;
20        for (int i = index + 1; i <= length; i++) {
21            if (setDict.contains(s.substring(index, i))) {
22                queue.add(i);
23            }
24        }
25    }
26    return false;
27}