Word Break
题目大意
给定一个目标字符串和一组字符串，判断目标字符串能否拆分成数个字符串，这些字符串都在给定的那组字符串中。
解题思路
动态规划
代码
class Solution(object): def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: bool """ n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(n): for j in range(i, -1, -1): print j, i, s[j:i + 1], dp if dp[j] and s[j:i + 1] in wordDict: dp[i + 1] = True break print '-----loop-----' return dp[n] 复制代码
输出：
0 0 l [True, False, False, False, False, False, False, False, False] -----loop----- 1 1 e [True, False, False, False, False, False, False, False, False] 0 1 le [True, False, False, False, False, False, False, False, False] -----loop----- 2 2 e [True, False, False, False, False, False, False, False, False] 1 2 ee [True, False, False, False, False, False, False, False, False] 0 2 lee [True, False, False, False, False, False, False, False, False] -----loop----- 3 3 t [True, False, False, False, False, False, False, False, False] 2 3 et [True, False, False, False, False, False, False, False, False] 1 3 eet [True, False, False, False, False, False, False, False, False] 0 3 leet [True, False, False, False, False, False, False, False, False] -----loop----- 4 4 c [True, False, False, False, True, False, False, False, False] 3 4 tc [True, False, False, False, True, False, False, False, False] 2 4 etc [True, False, False, False, True, False, False, False, False] 1 4 eetc [True, False, False, False, True, False, False, False, False] 0 4 leetc [True, False, False, False, True, False, False, False, False] -----loop----- 5 5 o [True, False, False, False, True, False, False, False, False] 4 5 co [True, False, False, False, True, False, False, False, False] 3 5 tco [True, False, False, False, True, False, False, False, False] 2 5 etco [True, False, False, False, True, False, False, False, False] 1 5 eetco [True, False, False, False, True, False, False, False, False] 0 5 leetco [True, False, False, False, True, False, False, False, False] -----loop----- 6 6 d [True, False, False, False, True, False, False, False, False] 5 6 od [True, False, False, False, True, False, False, False, False] 4 6 cod [True, False, False, False, True, False, False, False, False] 3 6 tcod [True, False, False, False, True, False, False, False, False] 2 6 etcod [True, False, False, False, True, False, False, False, False] 1 6 eetcod [True, False, False, False, True, False, False, False, False] 0 6 leetcod [True, False, False, False, True, False, False, False, False] -----loop----- 7 7 e [True, False, False, False, True, False, False, False, False] 6 7 de [True, False, False, False, True, False, False, False, False] 5 7 ode [True, False, False, False, True, False, False, False, False] 4 7 code [True, False, False, False, True, False, False, False, False] -----loop----- 复制代码
可以看到，把dp[0]设置为True是一个分割，每一个true都是一个分割点。
Word Break II
题目大意
给定一个目标字符串和一组单词，将目标字符串进行拆分，要求拆分出的部分在那个单词组中，拆分后的单词用空格隔开，给出所有可能的拆分情况。
解题思路
动态规划+深度优先 参考：www.cnblogs.com/zuoyuan/p/3…这道题不只像word break那样判断是否可以分割，而且要找到所有的分割方式，那么我们就要考虑dfs了。
不过直接用dfs解题是不行的，为什么？因为决策树太大，如果全部遍历一遍，时间复杂度太高，无法通过oj。
那么我们需要剪枝，如何来剪枝呢？使用word break题中的动态规划的结果，在dfs之前，先判定字符串是否可以被分割，如果不能被分割，直接跳过这一枝。实际上这道题是dp+dfs。
代码
class Solution(object): def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: List[str] """ Solution.res = [] self.dfs(s, wordDict, '') return Solution.res def dfs(self, s, wordDict, stringlist): if self.check(s, wordDict): # 如果s已经切完，则加入最后结果集 if len(s) == 0: Solution.res.append(stringlist[1:]) for i in range(1, len(s)+1): if s[:i] in wordDict: print stringlist+' '+s[:i] self.dfs(s[i:], wordDict, stringlist+' '+s[:i]) def check(self, s, wordDict): dp = [False for i in range(len(s)+1)] dp[0] = True # 这里循环是len(s)，使得该check函数变成了只要有单词在里面就验证成功，和wordbreak有所不同！ for i in range(len(s)): for j in range(i, -1, -1): if dp[j] and s[j:i + 1] in wordDict: dp[i + 1] = True break return dp[len(s)] 复制代码
输出：
cat cat sand cat sand dog cats cats and cats and dog
