# Word Break II

DFSDP

## # Solution

Let $n$ be the length of the string s, and $m$ be the number of words in wordDict.

### # DFS

Both of the dfs methods below work.

Complexity

time: $O(nm)$
space: $O(n)$

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
return self.dfs(s, wordDict, {})

def dfs(self, s, wordDict, memo):
if s in memo: return memo[s]
if not s: return []
res = []
if s in wordDict: res.append(s)
for i in range(1, len(s)+1):
if s[:i] not in wordDict: continue
for sg in self.dfs(s[i:], wordDict, memo):
res.append(s[:i] + ' ' + sg)
memo[s] = res
return res

def dfs(self, s, wordDict, memo):
if s in memo: return memo[s]
if not s: return []

res = []
for word in wordDict:
if not s.startswith(word):
continue
if len(word) == len(s):
res.append(word)
else:
resultOfTheRest = self.dfs(s[len(word):], wordDict, memo)
for item in resultOfTheRest:
item = word + ' ' + item
res.append(item)
memo[s] = res
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32