Word Break
franklinqin0 DFSDP
# Solution
Let be the length of the string s
, and be the number of words in wordDict
.
# Vanilla DFS (TLE)
Complexity
time:
space:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
def dfs(start):
if start == len(s):
return True
for word in wordDict:
n = len(word)
if start + n > len(s):
continue
if s[start: start + n] != word:
continue
if dfs(start + n):
return True
return False
return dfs(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# Memoized DFS
Complexity
time:
space:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
def dfs(start):
if start == len(s):
return True
if memo[start] != None:
return memo[start]
for word in wordDict:
n = len(word)
if start + n > len(s):
continue
if s[start: start + n] != word:
continue
if dfs(start + n):
memo[start] = True
return True
memo[start] = False
return False
memo = [None for _ in range(len(s))]
return dfs(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19