题目大意：给定一个字符串和一个字典，查看字符串能不能由字典里的单词构成。
解题思路：假如前\(i\)个字符串(左半部分)可以被字典里的单词分解，从\(i\)字符串后面的字符串(右半部分)也在字典里，那么这个字符串就有解。
动态规划
假如前\(i\)个字符串(左半部分)可以被字典里的单词分解，从\(i\)字符串后面的字符串(右半部分)也在字典里，那么这个字符串就有解。
如果string没有padding，因为f有padding，那么f[j]对应的应该是s[j-1]的位置.所以新的string应该从j位置开始。
def wordBreak(self, s, wordDict):
n = len(s)
# padding
f = [0 for _ in range(n + 1)]
f[0] = 1
for i in range(1, n + 1):
for j in range(0, i):
if (f[j] == 1):
new_s = s[j:i] #s[j, ..., i-1]
# python slice diff from c++
if new_s in wordDict:
f[i] = 1
break
return f[n]
如果string前面有 space padding，那么f和s都是从同样的位置开始。要注意的是python的slices[j:i]的话i是不包含的。如果要包含i，那么要用slices[j:i+1]
def wordBreak(self, s, wordDict):
n = len(s)
s = ' ' + s
# padding
f = [False for _ in range(n + 1)]
f[0] = True
for i in range(1, n + 1):
for j in range(0, i):
if (f[j] == True):
new_s = s[(j+1):(i+1)] #s[j+1, ..., i]
if new_s in wordDict:
f[i] = True
break
return f[n]
revisit
记忆化递归，把前面的结果存在mem_里面
def wordBreak(self, s, wordDict):
self.mem_ = {}
def dfs(s, wordDict):
# recursion termination conditions
# 1. if s already calculated in mem_, dont need to recalculate
if s in self.mem_:
return self.mem_[s]
# 2. if s is in wordDict, then it is true
if s in wordDict:
self.mem_[s] = True
return True
# try every break porint, break to left and right
for j in range(1, len(s)):
left = s[:j]
right = s[j:]
if right in wordDict and dfs(left, wordDict):
self.mem_[s] = True
return True
self.mem_[s] = False
return False
return dfs(s, wordDict)