LeetCode-140-单词拆分 II

原题链接： https://leetcode-cn.com/problems/word-break-ii/

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

image.png

解题思路：

1. 动态规划+回溯；
2. 单独用回溯算会出现“超出时间限制”错误，因此先用动态规划判断dp[-1]==True；
3. 如果可以拆分，再使用回溯计算结果，否则返回[]。

Python3代码：

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        size = len(s)
        dp = [False for i in range(size+1)]
        dp[0] = True
        word_set = set(wordDict)
        for i in range(1,size+1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break

        res = []
        if dp[-1]:
            def func(begin, track):
                if len(''.join(track))==size:
                    res.append(' '.join(track))
                    return 
                for i in range(begin, size):
                    if s[begin:i+1] in word_set:
                        func(i+1, track+[s[begin:i+1]])
            func(0, [])
        return res