Solution
from typing import List
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
def insert(self, word):
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return False
node = node.children[idx]
return node.is_end
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
def dfs(s):
if not s:
return [[]]
res = []
for i in range(1, len(s) + 1):
if trie.search(s[:i]):
for v in dfs(s[i:]):
res.append([s[:i]] + v)
return res
trie = Trie()
for w in wordDict:
trie.insert(w)
ans = dfs(s)
return [' '.join(v) for v in ans]
if __name__ == "__main__":
sol = Solution()
print(sol.wordBreak("catsanddog", ["cat","cats","and","sand","dog"]))
# ['cat sand dog', 'cats and dog']
print(sol.wordBreak("pineapplepenapple", ["apple","pen","applepen","pine","pineapple"]))
# ['pine apple pen apple', 'pine applepen apple', 'pineapple pen apple']
print(sol.wordBreak("catsandog", ["cats","dog","sand","and","cat"]))
# []