---
# System prepended metadata

title: LC 139. Word Break
tags: [medium, leedcode, DP, python, c++]

---

# 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
```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++
```cpp=
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 分析:
```cpp=
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
