# 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
```

{% hint style="info" %}
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)
{% endhint %}

```cpp
// 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();
}
```

```cpp
// 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();
}
```

```cpp
// 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);
}
```
