题目描述

给定一个非空字符串 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1 – Top-down

这道题是“139-单词拆分”的升级版本，在第139题中使用了Bottom-up和Top-down两种解法。但是这道题要求给出所有可能的组合，如果我们使用Bottom-up解法，会导致计算过程中产生大量不需要的中间结果。这也是Bottom-up的缺点，需要将所以子问题计算完成，才能够求解大规模的问题。而Top-down类似于按需计算，当发现有一个子问题没有被计算才会求解。

举一个例子，s=“aaab”，wordDict = [“a”]。这个例子很明显结果为空，因为无法用字典构成任何句子。如果使用Bottom-up方法，需要把子问题”a”、”aa”、”aaa”都算出来，才能计算”aaab”。最后发现这个字符串无法构成句子，那么前面的计算都白费了。 如果使用Top-down方法，将s=”aaab”拆分为”a”和”aab”、”aa”和”ab”、”aaa”和”b”，会发现没有任何一个拆分使得右半部分在字典中存在，就不会继续计算了。这就是使用Top-down方法的优点-避免没必要的计算。

题目139要求寻找字符串s能否用给定的词典组成，而这道题要求找出字符串s所有可能构成的句子，我们只需要对题目139的Top-down解法稍微进行修改就可以作为这道题目的答案。主要修改变量cache的数据结构，以及for循环的逻辑

第139题使用Map<String, Boolean> cache存储计算过的中间结果，这道题目要求计算组成的句子，所以我们需要把它改成Map<String, List<String>> cache，因为同一个前缀能够组成多个句子，所以需要使用列表存储。在第139题中，只要求判断s能被字典构成就可以退出循环。

 for (int splitIdx = 0; splitIdx < s.length(); splitIdx++) {
    if (wordBreak(s.substring(0, splitIdx), wordSet) && wordSet.contains(s.substring(splitIdx))) {
        cached = true;
        break; //找到s的一个解就可以退出
}

但是这道题目需要求得全部解，还需要把解存储起来，所以不能找到一个解就退出。首先枚举字符串s的分割点splitIdx，将字符串分割为前半部分s[0…splitIdx)和suffix = s[splitIdx…|s|)。如果前半部分能够组成句子，且后半部分suffix在字典中存在，那么将suffix追加到前半部分组成的句子列表。

for (int splitIdx = 0; splitIdx < s.length(); splitIdx++) {
    String suffix = s.substring(splitIdx);
    if (wordSet.contains(suffix)) {
        List<String> prefixList = wordBreak(s.substring(0, splitIdx), wordSet);
        for (String prefix : prefixList) {
            ans.add(prefix + " " + suffix);
        }
    }
}

例如s = “catsanddog“, wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]。s的前缀”catsand“能够用字典构成句子{“cat sand”, “cats and”}，且suffix = “dog”在字典中存在，那么s就可以构成句子{“cat sand”, “cats and”}.append(suffix) = {“cat sand suffix”, “cats and suffix”}。全部代码如下：

class Solution {
    private Map<String, List<String>> cache = new HashMap<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        return wordBreak(s, new HashSet<>(wordDict));
    }

    private List<String> wordBreak(String s, Set<String> wordSet) {
        List<String> ans = cache.get(s);
        if (ans != null)
            return ans;

        ans = new ArrayList<>();
        // 如果s本身就在字典中，需要加入cache，因为这是base case
        if (wordSet.contains(s))
            ans.add(s);
        // 对于s寻找一个分割点
        for (int splitIdx = 0; splitIdx < s.length(); splitIdx++) {
            String suffix = s.substring(splitIdx);
            if (wordSet.contains(suffix)) {
                // prefixList存储了前缀组成句子的列表，如果前缀不能组成句子则列表为空
                List<String> prefixList = wordBreak(s.substring(0, splitIdx), wordSet);
                for (String prefix : prefixList) {
                    ans.add(prefix + " " + suffix);
                }
            }
        }
        // 当计算完成，才能将answer存入cache中。
        cache.put(s, ans);
        return ans;
    }
}