> For the complete documentation index, see [llms.txt](https://liuxue2010.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuxue2010.gitbook.io/data-structure-and-algorithms/dynamic-programming-ii/word-break.md).

# Word Break

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

## Example

Given s = "lintcode", dict = \["lint", "code"].

Return true because "lintcode" can be break as "lint code".

## Solution

f\[i - j] and s\[i - j:i] 表示从后面倒数第一个，第二个第三个，依次从后往前去比较而F\[j] 从前比较，由于j表示前j个这时后面的s\[j-1+1: i-1+ 1] so S\[i-j: i]

state: f\[i]表示“前i”个字符能否被完美切分\
function: f\[i] = OR{f\[j]}, j < i, j+1 \~ i是一个词典中的单词initialize: f\[0] = true\
answer: f\[s.length()]

```
class Solution:
    # @param s: A string s
    # @param dict: A dictionary of words dict
    def wordBreak(self, s, dict):
        if len(dict) == 0:
            return len(s) == 0

        n = len(s)
        f = [False] * (n + 1)
        f[0] = True

        maxLength = max([len(w) for w in dict])

        for i in range(1, n + 1):
            for j in range(1, min(i, maxLength) + 1):
                if f[i - j] and s[i - j:i] in dict:
                    f[i] = True
                    break

        return f[n]
```