题目来源：

　　https://leetcode.com/problems/word-break-ii/

---

 

题意分析：

　　给定一个字符串s和一个字典dict（set），将所有将s有字典dict组成的结果输出。比如s = "catsanddog",

dict = ["cat", "cats", "and", "sand", "dog"].那么结果是["cats and dog", "cat sand dog"]。

---

 

题目思路：

　　我们将问题细化，如果s[:i]在字典dict里面，那么结果就是s[:i]和 solve（s[i + 1:]，dict)的笛卡尔乘积。如果直接实现，那么时间复杂度较高，所以这里用动态规划的思想，判断一个字符串是否可以有字典组成。

---

 

代码（python）：

class Solution(object):    def isp(self,s,dict):        dp = [False for i in range(len(s) + 1)]        dp[0] = True        for i in range(1,len(s) + 1):            for j in range(0,i):                if dp[j] and s[j:i] in dict:                    dp[i] = True        return dp[len(s)]    def wordBreak(self, s, wordDict):        """        :type s: str        :type wordDict: Set[str]        :rtype: List[str]        """        ans,tmp = [],""        if s in wordDict:            ans.append(s)        for i in range(len(s)):            tmp += s[i]            if tmp in wordDict:                if self.isp(s[i + 1:],wordDict):                    t = self.wordBreak(s[i+1:],wordDict)                    for j in t:                        ans.append(tmp + " " + j)        return ans