0

## 【小馬的LeetCode練功坊】139, 140 Word Break，依單字清單斷句

``````Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
(文字清單內的字可重複使用)
``````

``````s = "catsanddog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
``````

"catsanddog"為"cats"與"cat"的開頭，
「"catsanddog"的所有分解」就可以遞迴地拆解成
"cats"與「"anddog"的所有分解」+ "cat"與「"sanddog"的所有分解」，

# 純遞迴- 超時

``````class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
res = []
for word in wordDict:
if s.startswith(word):
res += [s] if s==word else [word+' '+seg for seg in self.wordBreak(s[len(word):], wordDict)]
return res
``````

# 用dict記錄答案- AC

``````class Solution:
def __init__(self):
self.wordMap = {}

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
res = []
for word in wordDict:
if s.startswith(word):
tail_word = s[len(word):]
if tail_word in self.wordMap:
res += [word+' '+seg for seg in self.wordMap[tail_word]]
else:
res += [s] if s==word else [word+' '+seg for seg in self.wordBreak(tail_word, wordDict)]
self.wordMap[s] = res
return res
``````