> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/ix.-dynamic-programming/139.-word-break.md).

# 139. Word Break

\# Medium

{% hint style="success" %}
The problem is where to cut in this string. Record from start to end, if the substring `[0: i]` can do word break. The result is `[0: len(s)-1]`.
{% endhint %}

### Solution:

1. Define a list `canSegement[False]*(len(s)+1)` to do DP, set `canSegement[0]=True`.
2. Two-layer for loop to fill in all elements of canSegment. Cut from `[0:i]`, if substring before cut can segement and substring after cut is contained in `wordDic`, then `canSegment[i]=True`. 
3. `canSegment[len(s)]` is the result.

![Because canSegment\[j\] = True and {pe} is not in wordDic, canSegment\[i\] = False](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-M9zxaKzz82J4Y6eeifm%2F-MA-FNU8EIvLcknxn7wX%2F1592363411998.jpg?alt=media\&token=4a947255-af5b-404c-96e9-f3b937873377)

{% tabs %}
{% tab title="Python" %}

```python
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        canSegment = [False]*(len(s)+1)
        canSegment[0] = True
        
        for i in range(1, len(s)+1):
            for j in range(0, i):
                if canSegment[j] == True and s[j:i] in wordDict:
                    canSegment[i] = True
                    break
                canSegment[i] = False
            
        return canSegment[len(s)]
```

{% endtab %}

{% tab title="Java(O(n^3)" %}

```java
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] canSegment = new boolean[s.length() + 1];
        Arrays.fill(canSegment, false);
        canSegment[0] = true;
        
        for(int end = 1; end <= s.length(); end ++)
            for(int start = 0; start < end; start ++) {
                if(canSegment[start] && wordDict.contains(s.substring(start, end))) {
                    canSegment[end] = true;
                    break;
                }
            }
        return canSegment[s.length()];
    }
}
```

{% endtab %}
{% endtabs %}