题目链接 : https://leetcode-cn.com/problems/word-break-ii/

题目描述:

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

思路:

动态规划:

自顶向下:

参照139. 单词拆分 | 题解链接

相关题型:139. 单词拆分

代码:

思路一:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        import functools
        if not wordDict:return []
        wordDict = set(wordDict)
        max_len = max(map(len, wordDict)) 
        @functools.lru_cache(None)
        def helper(s):
            res = []
            if not s:
                res.append("")
                return res
            for i in range(len(s)):
                if i < max_len and s[:i+1] in wordDict: 
                    for t in helper(s[i+1:]):
                        if not t:
                            res.append(s[:i+1])
                        else:
                            res.append(s[:i+1] + " " + t)
            return res    
        return helper(s)

java

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        int max_len = 0;
        for (String word : wordDict) max_len = Math.max(max_len, word.length());
        return helper(s, max_len, wordDict, new HashMap<String, LinkedList<String>>());
    }

    private List<String> helper(String s, int max_len, List<String> wordDict, HashMap<String, LinkedList<String>> cache) {
        if (cache.containsKey(s)) return cache.get(s);
        LinkedList<String> res = new LinkedList<>();
        if (s.length() == 0) {
            res.add("");
            return res;
        }
        for (int i = 0; i < s.length(); i++) {
            if (i < max_len && wordDict.contains(s.substring(0, i + 1))) {
                for (String tmp : helper(s.substring(i + 1), max_len, wordDict, cache))
                    res.add(s.substring(0, i + 1) + (tmp.isEmpty() ? "" : " ") + tmp);
            }
        }
        cache.put(s, res);
        return res;
    }
}