# LC 139. Word Break

### [Problem link](https://leetcode.com/problems/word-break/)

###### tags: `leedcode` `medium` `python` `c++` `DP`

Given a string <code>s</code> and a dictionary of strings <code>wordDict</code>, return <code>true</code> if <code>s</code> can be segmented into a space-separated sequence of one or more dictionary words.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

**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

**Constraints:**

- <code>1 <= s.length <= 300</code>
- <code>1 <= wordDict.length <= 1000</code>
- <code>1 <= wordDict[i].length <= 20</code>
- <code>s</code> and <code>wordDict[i]</code> consist of only lowercase English letters.
- All the strings of <code>wordDict</code> are **unique** .

## Solution 1
#### Python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[0] = True

        for i in range(len(s)):
            if dp[i]:
                for word in wordDict:
                    if s[i:i+len(word)] == word:
                        dp[i+len(word)] = True

        return dp[-1]

#### C++

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;

        for (int i = 0; i < s.size(); i++) {
            if (dp[i]) {
                for (string& word: wordDict) {
                    string subS = s.substr(i, word.size());
                    if (subS == word) {
                        dp[i + word.size()] = true;
                    }
                }
            }
        }
        return dp.back();
    }
};

>### Complexity
>n = s.length
>m = wordDict.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n^2 * m) | O(n) |

## Note
sol1:
Time Complexity 分析:

for (int i = 0; i < s.size(); i++) {  // => O(n)
    if (dp[i]) {
        for (string& word: wordDict) {  // => O(m)
            string subS = s.substr(i, word.size());  // => O(n)
            if (subS == word) {
                dp[i + word.size()] = true;
            }
        }
    }
}

所以Time Complexity = n * m * n