WORD BREAK II | LEETCODE # 140 | PYTHON DFS SOLUTION

In this video we are solving Word Break II. This question seems simple to solve but without understanding how to do it effectively can be a massive pain in the ass.
Since we have to explore and return all possible solutions we'll be going with a DFS + Memoization based solution. The code is actually quite simple so stay tuned for how to solve this Hard level question.

[@aliz166]

Great video! I ended up solving it using your logic from Word Break I, just having the queue be a tuple of the current string and an array of the words. Granted, there is no memoization here due to a string having multiple results. Is there a significant difference in doing this? TC in leetcode shows it's still pretty effiicent:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
queue = collections.deque([(s, [])])
res = []
while queue:
word, cur_res = queue.popleft()
if not word:
res.append(" ".join(cur_res))
for start in wordDict:
if word.startswith(start):
queue.append((word[len(start):], cur_res + [start]))
return res

[@davidmwangi4312]

Great Explanation. We can solve this problem with backtracking as well.

[@crackfaang]

This approach is essentially backtracking, I just call it DFS