[Leetcode][python]Word Break/Word Break II/单词拆分/单词拆分 II

╰半夏微凉° 2022-06-04 06:54 233阅读 0赞

# 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 #

## 题目大意 ##

给定一个目标字符串和一组单词，将目标字符串进行拆分，要求拆分出的部分在那个单词组中，拆分后的单词用空格隔开，给出所有可能的拆分情况。

## 解题思路 ##

动态规划+深度优先  
参考：[http://www.cnblogs.com/zuoyuan/p/3760804.html][http_www.cnblogs.com_zuoyuan_p_3760804.html]  
这道题不只像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

# 总结 #

[http_www.cnblogs.com_zuoyuan_p_3760804.html]: http://www.cnblogs.com/zuoyuan/p/3760804.html