# 140. Word Break II
"""
given a string 's' and a dictionary of strings 'wordDict', add spaces in 's'
to construct a sentence where each word is a valid dictionary word. return
all such possible sentences in any order. note that the same word in the
dictionary may be reused mutliple times in the segmentation.
"""
class Solution(object):
def dfs(self, s, wordDict, memo):
if s in memo:
return memo[s]
if not s:
return []
res = []
for word in wordDict:
if not s.startswith(word):
continue
if len(word) == len(s):
res.append(word)
else:
res_rest = self.dfs(s[len(word) :], wordDict, memo)
for item in res_rest:
item = word + " " + item
res.append(item)
memo[s] = res
return res
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
return self.dfs(s, wordDict, {})
if __name__ == "__main__":
obj = Solution()
print(obj.wordBreak(s="catsanddog", wordDict=["cat", "cats", "and", "sand", "dog"]))
print(
obj.wordBreak(
s="pineapplepenapple",
wordDict=["apple", "pen", "applepen", "pine", "pineapple"],
)
)
print(obj.wordBreak(s="catsandog", wordDict=["cats", "dog", "sand", "and", "cat"]))
