问题描述

给定一个非空字符串 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"]
输出:
[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

设 d(i) 为子串 s[i ... len(s)-1] 可以拆分成的句子的列表，状态转移方程为：

• 对于 wordDict 中的任意单词 word
• 如果 s[i ... len(s)-1] 以 word 开头
  • 如果两者长度相同，那么将 word 添加到 d(i)
  • 否则，如果 d(i+len(word)) 非空，那么在 d(i+len((word)) 中的每个元素的前面加上word + 空格，并将其添加到 d(i)

其中len(S) 表示字符串 S 的长度。

注意：使用哈希表保存已经计算过的子问题，否则会导致 TLE。

Python 实现

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        return self._word_break(0, s, wordDict, {})

    def _word_break(self, start, s, word_dict, d):
        if start in d:
            return d[start]

        d[start] = ret = []
        for word in word_dict:
            end_idx = start + len(word)
            if s[start: end_idx] == word:
                if end_idx == len(s):
                    ret.append(word)
                else:
                    for words in self._word_break(end_idx, s, word_dict, d):
                        ret.append(word + " " + words)
        return ret