Solution
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
n = len(s)
f = [True] + [False] * n
for i in range(1, n + 1):
f[i] = any(f[j] and s[j:i] in words for j in range(i))
return f[n]
if __name__ == "__main__":
sol = Solution()
print(sol.wordBreak("leetcode", ["leet","code"])) # True
print(sol.wordBreak("applepenapple", ["apple","pen"])) # True
print(sol.wordBreak("catsandog", ["cats","dog","sand","and","cat"])) # False
Solution
from typing import List
class Trie:
def __init__(self):
self.children: List[Trie | None] = [None] * 26
self.isEnd = False
def insert(self, w: str):
node = self
for c in w:
idx = ord(c) - ord('a')
if not node.children[idx]:
node.children[idx] = Trie()
node = node.children[idx]
node.isEnd = True
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
trie = Trie()
for w in wordDict:
trie.insert(w)
n = len(s)
f = [False] * (n + 1)
f[n] = True # 空串可以拆分
for i in range(n - 1, -1, -1):
node = trie
for j in range(i, n):
idx = ord(s[j]) - ord('a')
if not node.children[idx]:
break
node = node.children[idx]
if node.isEnd and f[j + 1]:
f[i] = True
break
return f[0]
if __name__ == "__main__":
sol = Solution()
print(sol.wordBreak("leetcode", ["leet","code"])) # True
print(sol.wordBreak("applepenapple", ["apple","pen"])) # True
print(sol.wordBreak("catsandog", ["cats","dog","sand","and","cat"])) # False