LeetCode.M139.单词拆分

LeetCode.M139.单词拆分

题目：

题目大意：

给定一个字符串 s 和一个单词列表 wordDict ，问是否能使用 wordDict 中的单词拼接出 s ，wordDict 中的单词可以使用多次，不要求全部都用到。

数据范围：

如图所示
1

---

一 、解法 ：

思路：

BFS ： 可以将 s 看做路径，将 wordDict 看做每次可以走的方向，使用 bfs 来判断是否能走到最后。

注意：需要使用记忆化来保证不重复走，假如当前走到了 i ，如果 i 已经被走过了，说明该情况已经被处理过，则跳过 i 。如果 i 没有被处理过，则正常走。

代码：

// bfs
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Deque<Integer> que = new ArrayDeque<>();
        //标记是否已经处理过了。
        boolean[] isVisted = new boolean[1010];
        //从0开始走
        que.add(0);
        while (!que.isEmpty()){
            int st = que.poll();
            //如果该情况被处理过，则跳过
            if (isVisted[st])
                continue;
            isVisted[st] = true;
            //正常走
            for (int i = 0; i < wordDict.size(); i ++ ){
                String to = wordDict.get(i);
                int k = st, j = 0;
                if (s.length() - k < to.length())
                    continue;
                for (; k < s.length() && j < to.length(); k ++ , j ++ ){
                    if (s.charAt(k) != to.charAt(j)){
                        break;
                    }
                }
                //如果走到了s的最后，且 word 也完整匹配上了，说明可以，返回true。
                if (k == s.length() && j == to.length())
                    return true;
                //将下一次的起点加入到队列中
                if (j == to.length()){
                    que.add(k);
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

时空复杂度分析等：

• 时间复杂度 : ？
• 空间复杂度 : O(n)

---

二 、解法 ：

思路：

思路和 bfs 一样，只不过使用 dfs

代码：

//dfs
class Solution {
    //标记该情况是否已经被处理过
    public boolean[] isVisited = new boolean[1010];
    String s;
    //使用set加快查找速度
    Set<String> wordDict;

    public boolean dfs(int st){
        //如果找到了s的最后，则说明可以，返回true
        if (st == s.length())
            return true;
        //如果该情况没有被处理过
        if (!isVisited[st]){
            isVisited[st] = true;
            //走以st为起点，以i - 1为终点的路程（这段路程要在wordDict中），然后递归的处理以i为起点的情况 
            for (int i = st + 1; i <= s.length(); i ++ ){
                if (wordDict.contains(s.substring(st, i)) && dfs(i)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        this.s = s;
        this.wordDict = new HashSet<>(wordDict);
        return dfs(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

时空复杂度分析等：

• 时间复杂度 : ？
• 空间复杂度 : O(n)

---

三 、解法 ：

思路：

为了方便处理，使 s = " " + s，这样 原s 的下标从 1 开始。

dp:

• 状态表示：f[i] ：表示 s 中从 1 到 i 的子字符串是否可以被 wordDict 拼接。

• 状态转移：思考 f[i] 可以由谁转移而来，由于只能使用 wordDict 中的单词，所以 f[i] 可以由 f[i - word.length] 转移而来，且 s 中从 i - word.length + 1 到 i 的字串必须与 word 相同才可以从 f[i - word.length] 转移。只要有一个 wordDict 中的单词可以转移到 f[i] 且 f[i - word.length] 为 true ，则 f[i] 为 true。

• 初始状态 f[0] = true。

代码：

class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
        //为了方便处理，下标从1开始。
        s = " " + s;
        int n = s.length();
        boolean[] f = new boolean[n];
        f[0] = true;
        for (int i = 1; i < n; i ++ ){
            for (int j = 0; j < wordDict.size(); j ++ ){
                String word = wordDict.get(j);
                if (i - word.length() >= 0){
                    f[i] = f[i] || (f[i - word.length()] && word.equals(s.substring(i - word.length() + 1, i + 1)));
                }
                if (f[i])
                    break;
            }
        }

        return f[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时空复杂度分析等：

• 时间复杂度 : O(n^2)

• 空间复杂度 : O(n)

题目链接：

139. 单词拆分 - 力扣（LeetCode）