140. Word Break II
今天開始恢復(fù)做難題焕盟，算了一下還有大概80道題這樣，每天保質(zhì)5道題介衔，20道總結(jié)一次恨胚。大概是20天的量。也許可以更快一些炎咖，畢竟有些難題只是中等題目的變種赃泡，不過一定要每一道難題都好好總結(jié)，如果不會(huì)的情況看了答案乘盼，第二天要手動(dòng)重寫急迂，這樣可以增加熟練度。還有一個(gè)原則是只考慮二十分鐘蹦肴，如果二十分鐘難題還沒有思路就去看答案僚碎。
這道題基本思路有，也知道用backtracking+memory阴幌，不過怎么加memory還是個(gè)技術(shù)活勺阐。
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
return self.dfs(s, wordDict, {})
def dfs(self, s, wordDict, m):
if s in m:
return m[s]
res = []
if not s:
return [""]
for word in wordDict:
if s.startswith(word):
sublist = self.dfs(s[len(word):], wordDict, m)
for sub in sublist:
if not sub:
res.append(word)
else:
res.append(word+" "+sub)
m[s] = res[:]
return res
