Daily LeetCode 140. Word Break II

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

Hard

问题描述：

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

思路及代码：

这是昨天那题的进阶版本，昨天的题目只是让我们判断是否能够将s正确切分，今天这题不仅需要判断能否正确划分，同时还要拿划分后的单词拼接成句子，并且要求输出所有可能的句子。

对于这一类的构造相关的问题，我们通常需要用递归来实现，同时，我们还需要基于上一题的结果对递归进行剪枝，降低时间复杂度。

我们定义一个helper函数，该函数的输入分别是当前字符串current_s，构造结果res，当前构造的句子path，判断结果dp以及单词词典wordDict；该函数将原字符串划分为两个部分，若前半部分符合划分条件，即前半部分在wordDict中，将前半部分加入到当前path，接着通过递归操作，判断后半部分。

代码如下：

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

            return dp

        def helper(current_s, res, path, dp, wordDict):
            if dp[-1] == 1:
                if not current_s:
                    res.append(path.strip())
                for i in range(1, len(current_s) + 1):
                    if current_s[:i] in wordDict:
                        helper(current_s[i:], res, path + " " + current_s[:i], dp, wordDict)

        if not s:
            return [""]
        res = []
        dp = wordBreak(s, wordDict)
        helper(s, res, "", dp, wordDict)

        return res