139. Word Break (Medium)

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

s = "leetcode",

dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution:

Updated: 9ms

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;
        for (string& a: wordDict) dict.insert(a);
        int n = s.size();
        vector<bool> dp(n+1, false);
        dp[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.count(s.substr(j, i-j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

version 2: 3ms

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> m;
        int maxlen = 0;
        for (string& word: wordDict) {
            m.insert(word);
            maxlen = max(maxlen, (int)word.size());
        }
        vector<bool> dp(s.size()+1,false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = i-1; j >= max(i-maxlen,0); --j) {
                string tmp = s.substr(j, i-j);
                if (dp[j] && m.count(tmp)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

Time Complexity: $$O(n^2)$$ Space Complexity: $$O(n)$$

接下来我们套用上面的思路来解这道题。首先我们要存储的历史信息res[i]是表示到字符串s的第i个元素为止能不能用字典中的词来表示，我们需要一个长度为n的布尔 bool 数组来存储信息。然后假设我们现在拥有res[0,...,i-1]的结果，我们来获得res[i]的表达式。思路是对于每个以i为结尾的子串，看看他是不是在字典里面以及他之前的元素对应的res[j]是不是true，如果都成立，那么res[i]为true，写成式子是

假设总共有n个字符串，并且字典是用HashSet来维护，那么总共需要n次迭代，每次迭代需要一个取子串的O(i)操作，然后检测i个子串，而检测是constant操作。所以总的时间复杂度是O(n^2)（i的累加仍然是n^2量级），而空间复杂度则是字符串的数量，即O(n)。代码如下：

Note: j从后往前找更快

bool wordBreak(string s, unordered_set<string>& wordDict) {
    int len = s.size();
    vector<bool> res(len+1, false);
    res[0] = true;
    for (int i = 1; i <= len; ++i) {
        for (int j = i-1; j >= 0; --j) {
            if (res[j] && wordDict.count(s.substr(j,i-j)) {
                res[i] = true;
                break;
            }
        }
    }
    return res[len];
}

if we find valid length of dict strings, we will reduce the time to 3 ms

(No need to check all length) j to longestWord

bool wordBreak(string s, unordered_set<string>& wordDict) {
    int len = s.size();

    int longestWord = 0;
    for(string word : wordDict){
        longestWord = max(longestWord, (int)word.size());
    }

    vector<bool> res(len+1, false);
    res[0] = true;
    for (int i = 1; i <= len; ++i) {
        for (int j = i-1; j >= max(i-longestWord, 0); --j) {
            if (res[j]) {
                if (wordDict.find(s.substr(j,i-j)) != wordDict.end()) {
                    res[i] = true;
                    break;
                }
            }
        }
    }
    return res[len];
}