140. 单词拆分 II

Difficulty
Hard
Tags
动态规划
URL
https://leetcode-cn.com/problems/word-break-ii/
Star
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
  • 分隔时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。
示例 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 动态规划

题目
🌗
139. 单词拆分 进阶版。需要记住每一天对应的具体状态。
题解
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        res = []
        s = "#" + s
        dp = [[] for _ in range(len(s))]
        dp[0].append("#")

        for i in range(1, len(s)):
            for j in range(0, i):
                if len(dp[j]) > 0 and s[j+1:i+1] in wordDict:
                    if j == 0:
                        dp[i].append(s[j+1:i+1])
                    else:
                        for k in range(len(dp[j])):
                            dp[i].append(dp[j][k]+" "+s[j+1:i+1])
        # print(dp)
        return dp[-1]