Solution to LeetCode 140 Word Break II.
LeetCode 140
Word Break II (Hard). [link]
Different from LC 139, this problem asks for all possible segmented results.
Recursion and memorization. To avoid large time complexity, we usually need a dictionary to store the results. Time complexity O(n*2^n), space complexity O(n*2^n).
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
def DP(s, res, wordDict, memo):
if s in memo: return memo[s]
if not s: return [[]]
res = []
for word in wordDict:
if s[:len(word)] != word:
continue
wordList = DP(s[len(word):], res, wordDict, memo)
for nxt in wordList:
res.append([word] + nxt)
memo[s] = res
return res
wordSet = set(wordDict)
res = []
memo = {}
lists = DP(s, res, wordSet, memo)
return [" ".join(words) for words in lists]
