LeetCode139-单词拆分

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/word-break/

中文链接：https://leetcode-cn.com/problems/word-break/

题目详述

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

说明：

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

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

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

题目详解

wordDict 中的单词没有使用的次数，因此这是一个完全背包（物品可以使用0次或无限次）问题。

01 背包和完全背包的区别在于，01 背包对物品的迭代是在最外层，而完全背包对物品的迭代是在最内层。这样可以保证 01 背包最多只能使用物品一次，完全背包可以使用物品多次。

方法一：动态规划。

  • boolean 数组 dp[i] 表示 s[0, i) 是否能被空格拆分为一个或多个在字典中出现的单词。例如 dp[1] 表示 s[0, 1) 也就是 s[0] 单独可以被拆分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00139 {

    // DP(完全背包)
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (String word : wordDict) {
                int preIndex = i - word.length();
                if (preIndex >= 0 && dp[preIndex] && word.equals(s.substring(preIndex, i))) {
                    dp[i] = dp[preIndex];
                }
            }
        }
        return dp[n];
    }
}

可以换一种方式写动态规划，将 wordDict 转化为 HashSet，加快查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00139 {

    // DP(完全背包)
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] f = new boolean[n + 1];
        f[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (f[j] && set.contains(s.substring(j, i))) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n];
    }
}

方法二：DFS + 剪枝。

  • s.startsWith(word, offset) 表示从 s 的 offset 处开始匹配，是否匹配。
  • 设置访问标志用于剪枝。 
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
public class LeetCode_00139 {

    // DFS + 剪枝（设置访问标志）
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) {
            return false;
        }
        boolean[] vis = new boolean[s.length() + 1];
        return dfs(s, 0, wordDict, vis);
    }

    private boolean dfs(String s, int offset, List<String> wordDict, boolean[] vis) {
        if (offset == s.length()) {
            return true;
        }
        vis[offset] = true;
        for (String word : wordDict) {
            // startWith 放前面先判断（offset + word.length() 可能会越界）
            if (s.startsWith(word, offset) && !vis[offset + word.length()]) {
                if (dfs(s, offset + word.length(), wordDict, vis)) {
                    return true;
                }
            }
        }
        return false;
    }
}