139. Word Break
139. Word Break
使用动态规划的思路，dp[i]表示s[:i]能不能被分割，那么计算dp[i]的时候，需要从j = 1开始，如果dp[j] == True 且s[j:i]在wordDict中，则dp[i] = True。
代码如下：
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
dp = [False for i in range(len(s)+1)]
dp[0] = True
for i in range(1, len(s)+1):
for j in range(i):
if dp[j] and s[j:i] in wordDict:
dp[j] = False
return dp[-1]
140. Word Break II
140. Word Break II
一般求一个结果，所有可能个数或者True/False，用动态规划，求所有可能结果，用回溯法。
代码如下：
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
res = []
trace = []
self.DFS(s, wordDict, res, trace, 0)
return res
def DFS(self, s, wordDict, res, trace, k):
if k == len(s):
res.append(' '.join(trace))
return
for i in range(k, len(s)):
if s[k:i+1] in wordDict:
trace.append(s[k:i+1])
self.DFS(s, wordDict, res, trace, i+1)
trace.pop()
上述代码Time Limit Exceeded
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
所以每一步都要记录一下，不然会有很多重复计算
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
memo = {}
return self.DFS(s, wordDict, memo)
def DFS(self, s, wordDict, memo):
if len(s) == 0:
return []
if s in memo:
return memo[s]
res = []
if s in wordDict:
res.append(s)
for i in range(1, len(s)):
partition = s[:i]
if partition not in wordDict:
continue
for other in self.DFS(s[i:], wordDict, memo):
res.append(partition + ' ' + other)
memo[s] = res
return res
