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

dp[i]代表s[0...i - 1]可否被拆分成wordDict中的字組合。 當要確認dp[i]的結果時，loop所有可能小於i的j，看看dp[j]是否能被拆分成wordDict的字的組合還有s[j...i - 1]是否能形成wordDict的一個字。 dp state transition: dp[i] = dp[j] && s.substr(j, i - j)

// Bottom-Up Dynamic programming
bool wordBreak(string s, vector<string>& wordDict) { // time: O(n^3); space: O(n)
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    int n = s.length();
    vector<bool> dp(n + 1, false); // dp[i] means s[0...i - 1] can be broken into segmentations
    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] && words.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp.back();
}

// Bottom-Up Dynamic programming
bool wordBreak(string s, vector<string>& wordDict) { // time: O(n^3); space: O(n)
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    int maxLen = 0; // max word length 
    for (const string& word : words) {
        maxLen = max(maxLen, (int)word.length());
    }
    int n = s.length();
    vector<bool> dp(n + 1, false); // dp[i] means s[0...i - 1] can be broken into segmentations
    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
        int limit = max(0, i - maxLen);
        for (int j = i - 1; j >= limit; --j) {
            if (dp[j] && words.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp.back();
}

// Top-down Dynamic Programming
bool helper(string& s, unordered_set<string>& words, int start, vector<int>& memo) {
    if (start >= s.length()) return true;
    if (memo[start] != -1) return memo[start];
    for (int i = start; i < s.length(); ++i) {
        if (words.count(s.substr(start, i - start + 1)) && helper(s, words, i + 1, memo))
            return memo[start] = 1;
    }
    return memo[start] = 0;
}
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    vector<int> memo(s.size(), -1);
    return helper(s, words, 0, memo);
}