Word Break II
franklinqin0 DFSDP
# Solution
Let be the length of the string s
, and be the number of words in wordDict
.
# DFS
Both of the dfs
methods below work.
Complexity
time:
space:
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
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