Backtracking with memoization. Build sentences recursively.
def wordBreak(s, wordDict): wordSet = set(wordDict) memo = {}
def backtrack(start):
if start in memo:
return memo[start]
if start == len(s):
return [""]
results = []
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in wordSet:
for sentence in backtrack(end):
if sentence:
results.append(word + " " + sentence)
else:
results.append(word)
memo[start] = results
return results
return backtrack(0)
worst case. space.