> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/array/sequence.md).

# Word Break

*  State: f\[i]表示前i个位置/数字/字符,第i个...
* 一般answer是f(n)而不是f(n-1)

## 139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

#### BackTracking

* Brute Force: 2^n => see [explain](https://leetcode.com/problems/word-break/discuss/169383/The-Time-Complexity-of-The-Brute-Force-Method-Should-Be-O\(2n\)-and-Prove-It-Below)
* TC: (length of s) \* (size of wordDict) 
* SC: n, depth of str

```python
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    visit = [-1] * len(s)
    dic = set(wordDict)
    return self.backtracking(s, dic, 0, visit)


def backtracking(self, s, dic, start, visit):
    if start == len(s): return True
    if visit[start] != -1: return visit[start]

    for end in range(start+1, len(s)+1):
        if s[start:end] in dic and self.backtracking(s, dic, end, visit):
            visit[start] = 1
            return visit[start]
    visit[start] = 0
    return visit[start]
```

#### DP

* State: f\[i] 表示前i個字被完美切分
* function: f\[i] = OR{f\[j]}, j\<i && j+1 to i is a word
* Init: f\[0] = true
* Ans: f\[n]

```java
public boolean wordBreak(String s, List<String> wordDict) {
    boolean[] f = new boolean[s.length()+1];

    f[0] = true;

    for(int i=1; i<=s.length(); i++){ // f length = n+1
        for(int j=0; j<i; j++){
            if(f[j]){
                String sub = s.substring(j, i);
                if (wordDict.contains(sub)){
                    f[i] = true;
                    break;
                }
            }
        }
    }
    return f[s.length()];
}
```

## 140 Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Backtracking

O: (length of s) \* (size of wordDict) \* (number of answer)

```python
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
    map = {}
    map[len(s)] = ''
    dic = set(wordDict)
    
    return self.backtracking(s, 0, map, dic)


def backtracking(self, s, start, map, dic):
    if start in map:
        return map[start]
    
    res = []
    for end in range(start+1, len(s)+1):
        if s[start:end] in dic:
            for l in self.backtracking(s, end, map, dic):
                sen = s[start:end] + (' ' if l != '' else '') + l
                res.append(sen)
                
    map[start] = res
    return map[start]
```