140. Word Break II是一道难度为hard的题，不太好写。
题目大意：单词分割，给定一个字符串和一个字典，如果字符串能由字典里的单词组成，那么返回组成的单词。最后要求返回所有的可能的解。
跟139. Word Break不同的是，这道题要找到解，而且要找出所有的解。
动态规划
对每个分割点，如果右边在字典里，同时如果左边有解，那么这个分割有效
对左边采取同样的办法，先分割成左右，然后看右边是不是在字典里，在的话再检查左边
如此迭代下去
注意的是左边可能不止一个分割办法，最要要把右边跟左边的所有可能解加在一起，这样才能找到所有的解
def wordBreak(self, s, wordDict):
self.mem_ = {}
def dfs(s, wordDict):
if s in self.mem_:
return self.mem_[s]
ans = [] # answer for curr s
if s in wordDict:
ans.append(s)
for j in range(1, len(s)):
right = s[j:]
if right not in wordDict:
continue
left = s[:j]
left_ans = [x + ' ' + right for x in dfs(left, wordDict)]
ans += left_ans
self.mem_[s] = ans
return self.mem_[s]
return dfs(s, wordDict)
Solution().wordBreak("catsanddog", ['cat', 'cats', 'and', 'sand', 'dog'])