140. 单词拆分 II

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

解法一：dp+回溯

借鉴139的dp做法，先求出dp数组，再根据dp结果回溯输出所有情况

class Solution:
    def wordBreak(self, s: 'str', wordDict: 'List[str]') -> 'List[str]':
        dp = [False] * (len(s) + 1)  #记录表
        dp[0] = True

        maxLen = 0
        for word in wordDict:
            maxLen = max(maxLen, len(word))

        for i in range(1, len(s) + 1):
            for j in range(max(i - maxLen, 0), i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
                    
        tmp = []  #记录回溯内容
        self.res = []
        #重要，先检测是否能拆分，否则超时
        if dp[len(s)] == True:
            self.backtrack(0, tmp, s, wordDict, dp)
        return self.res
    
    #下标idx之前的串都能拆分
    def backtrack(self, idx, tmp, s, wordDict, dp):
        if idx == len(s):
            self.res.append(" ".join(tmp))
        #遍历idx及之后的部分
        for i in range(idx, len(s) + 1):
            #下一次递归从i开始
            if dp[idx] and s[idx:i] in wordDict:
                tmp.append(s[idx:i])
                self.backtrack(i, tmp, s, wordDict, dp)
                tmp.pop()