[LeetCode] 139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Example 1:
Input: s = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.

Example 2:
Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.
Note that you are allowed to reuse a dictionary word.

Example 3:
Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: false

单词拆分.

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是 dp, dp[i] 的含义是以 index = i 位置上那个字母结尾的字符串是否能被 list 中的单词拼接。初始化 dp[0] = true。接下来用另外一个指针 j 去扫描 0 - i 范围内所有的的 substring。如果 dp[j] = true && substring(j, i) 也在 wordDict 存在，则dp[i] = true。

跑一下第 1 个例子，

Input: s = "leetcode", wordDict = ["leet", "code"]

DP 数组最后的输出值如下，当 i 指针遍历到 c（index = 4），j 指针还在 0 的时候，此时因为 dp[0] = true && s.substring(j, i) = s.substring(0, 4) = “leet” 也存在于 wordDict，所以可以将 dp[4] 标记为 true。

[true, false, false, false, true, false, false, false, true]

复杂度

时间O(n^2)
空间O(n)

代码

Java实现

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        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++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

JavaScript实现

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
    const dp = new Array(s.length + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            const word = s.slice(j, i);
            if (dp[j] == true && wordDict.includes(word)) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length];
};

优化

我们注意到上一种方法可行，但是效率很低。因为 substring 函数会找到一些根本不存在于 wordDict 中的单词，比如我们可以找到 leet，但是我们再去找 leetc 是没有意义的，这样一个字母一个字母地加，效率很低。一个优化的方法是我们遍历位置的同时，第二层 for 循环遍历的是每个单词。比如一开始初始化 dp[0] = true，然后对于 wordDict 中的每个单词 word，我要找的下一个 substring 是 s.substring(i + word.length())。这样我就可以按照当前单词的长度，对这个环节的搜索加速。

代码

Java实现

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int lo = 0; lo < n; lo++) {
            if (!dp[lo]) {
                continue;
            }
            for (String word : wordDict) {
                int hi = lo + word.length();
                // 因为substring是左闭右开的区间所以要判断hi <= n
                if (hi <= n && s.substring(lo, hi).equals(word)) {
                    dp[hi] = true;
                }
            }
        }
        return dp[n];
    }
}