140. Word Break II
今天开始恢复做难题，算了一下还有大概80道题这样，每天保质5道题，20道总结一次。大概是20天的量。也许可以更快一些，毕竟有些难题只是中等题目的变种，不过一定要每一道难题都好好总结，如果不会的情况看了答案，第二天要手动重写，这样可以增加熟练度。还有一个原则是只考虑二十分钟，如果二十分钟难题还没有思路就去看答案。
这道题基本思路有，也知道用backtracking+memory，不过怎么加memory还是个技术活。
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
