Word Break
- 2 min read
- LC-Medium
- Dynamic Programming
3 years ago
Solution
- Doing the Depth-first Search from the string will lead to a lot of complications, because you could have examples like
s = "aaaaaaa"andwordDict = ["aaaa","aaa"]. In this case, it becomes really messy when during your branching, whether you stop the current word ataaaor continue and buildaaaa. The following code I wrote worked for the first 3 test cases but for the case I just mentioned it did not work
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
word_dict = set(wordDict)
memo = {}
def dfs(i, cur_word):
if i in memo:
return memo[i]
if i == len(s):
if cur_word in word_dict:
return True
print('bruh', cur_word)
return False
if cur_word in word_dict:
cur_word = ''
memo[i] = dfs(i + 1, cur_word + s[i])
return memo[i]
return dfs(0, '')
- Instead, work from the wordDict instead, have a current index and only move it forward when you see a matching word
- You can use memoization to avoid repeated work, because if you already dealt with an index, you don't have to deal with it again.
- It's not easy to see overlapping branches with the examples given but trust me, for certain words, there will be a lot of overlap, i.e. reaching the same indexing from different start points, so it's important to use memoization here
Solution (Top-down Memoization)
- Simply, for each word in
wordDict, check if there's a match substring from current index, and if so, recur futher - If we can reach the end of the string, it means a word break is possible, so return True
| Time | Space | Explanation |
|---|---|---|
O() | O() | |
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
@cache
def dp(i):
if i >= len(s):
return True
for word in wordDict:
if s[i : i + len(word)] == word and dp(i + len(word)):
return True
return False
return dp(0)
# Another implementation without the @cache decorator
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
memo = {}
def dfs(i):
if i >= len(s):
return True
if i not in memo:
memo[i] = False
for word in wordDict:
if s[i : i + len(word)] == word and dfs(i + len(word)):
memo[i] = True
return memo[i]
return dfs(0)