Link: https://leetcode.com/problems/word-break-ii/
Solution:
DSA: DFS, subarray, set, grow, shrink
Intuition
The key to understanding this problem is realizing that we can shrink s, and grow the current sentence.
For example:
word_dict = ['cat', 'cats', 'and', 'sand', 'dog']
s = 'catsanddog'curr_s | s
---------------------
'' catsanddog
cats anddog
cats and dog
cats and dog ''
So we can construct our recursion following the grow/shrink pattern. And when len(s) == 0, we have taken everything we can from it, which means curr_s is a valid sentence!
In a recursive function, we would check all substrings of s starting at 0 if its a word in word_dict, if it is, then we shrink s and grow curr_s, and recursively call on those parameters.
Implementation
def word_break(s, word_dict):
word_dict = set(word_dict)
def dfs(s, curr_s):
if len(s) == 0:
return [curr_s[-1]] #remove the trailing space
res = []
for i in range(1, len(s)+1):
potential_word = s[:i]
if potential_word in word_dict:
sentence = dfs(s[i:], curr_s + potential_word + ' ')
res += sentence
return res
return dfs(s, '')Visual
Review 1
We can also use back tracking for this problem for a minor boost in memory efficiency.
Implementation (back tracking)
def word_break2(s, wordDict):
res = []
words = set(wordDict)
sent = []
def dfs(i):
if i == len(s):
res.append(' '.join(sent))
return
word = ''
for j in range(i, len(s)):
word += s[j]
if word in words:
sent.append(word)
dfs(j+1)
sent.pop()
dfs(0)
return res