140 - Word Break II
Written on January 13, 2020
Tweet
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
from functools import lru_cache
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
@lru_cache(None)
def helper(string):
if not string:
return []
ret = []
for word in wordDict:
if string.startswith(word):
if len(string) == len(word):
ret.append(word)
else:
ret.extend([word + " " + w for w in helper(string[len(word):])])
return ret
return helper(s)