0140：单词拆分 II（★★）

力扣第 140 题

题目

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

示例 1：

输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]

示例 2：

输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
输出:[]

提示：

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s 和 wordDict[i] 仅有小写英文字母组成
• wordDict 中所有字符串都 不同

相似问题：

• 0139：单词拆分
• 0472：连接词

分析

0139 升级版，改下递推的值即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        f = [[] for _ in range(n+1)]
        f[0] = [[]]
        vis = set(wordDict)
        for i in range(1,n+1):
            for j in range(max(0,i-10),i):
                if s[j:i] in vis:
                    f[i].extend(sub+[s[j:i]] for sub in f[j])
        return [' '.join(A) for A in f[-1]]

37 ms