> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/1-200/139.-dan-ci-chai-fen.md).

# 139. 单词拆分

[https://leetcode-cn.com/problems/word-break](https://leetcode-cn.com/problems/word-break/comments/)

## 解法一：回溯

显然超时

## 解法二：dp

用布尔变量`dp[i]`表示i之前的串`s[0:i]`是否能被拆分，i从1到n-1一次遍历，j从0到i，检测`s[j:i]`是否存在于字典中。若`dp[j]`为True且`s[j:i]`存在于字典中，则`dp[i]`也为True

```python
class Solution:
    def wordBreak(self, s: 'str', wordDict: 'List[str]') -> 'bool':
        dp = [False] * (len(s)+1)
        dp[0] = True  #初始化，空串能被任意拆分
        for i in range(1, len(s)+1):
            for j in range(0, i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break  #得到一个i拆分即可，进入i+1
        return dp[len(s)]
                    
```

优化：

对于以上代码可以优化。每次并不需要从`s[0]`开始搜索。因为`wordDict`中的字符串长度是有限的。只需要从`i-maxLen`开始搜索就可以了。

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