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 multiple times in the segmentation.
Example 1: Input: s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”] Output: [“cats and dog”,“cat sand dog”]
- code dp tabluation
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
ansList = [[[None]]] * (len(s) + 1) # [[[None]], [[None]], [[None]]...]
ansList[0] = [[]]
for i in range(len(ansList)):
if ansList[i] != [[None]]:
for word in wordDict:
if s[i:].startswith(word):
if ansList[i + len(word)] == [[None]]:
ansList[i + len(word)] = [temp + [word] for temp in ansList[i]]
else:
ansList[i + len(word)].extend([temp + [word] for temp in ansList[i]])
if ansList[-1] == [[None]]: return []
return [" ".join(i) for i in ansList[-1]]
- code dp
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
res = []
def helper(target, path):
if not target:
res.append(path)
for word in wordDict:
if target.startswith(word):
helper(target[len(word):], path + [word])
helper(s, [])
return [" ".join(i) for i in res]
- code bfs
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
wordDictList = {}
for word in wordDict:
wordDictList[word] = [[word]]
q = collections.deque(wordDict)
while q:
cur = q.popleft()
if s.startswith(cur):
for word in wordDict:
next = cur + word
if s.startswith(next):
q.append(next)
for tempList in wordDictList[cur]:
if next not in wordDictList:
wordDictList[next] = [tempList + [word]]
else:
if tempList + [word] not in wordDictList[next]:
wordDictList[next].append(tempList + [word])
if s not in wordDictList: return []
return [" ".join(i) for i in wordDictList[s]]