[LeetCode每日一题]140. Word Break II

题目如下：

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.

Example 1:

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

140. Word Break II
这道题在139. Word Break的基础上要求返回所有符合要求的句子。这道题同样可以用动态规划解决。设状态空间为dp[s.length+1],dp[i]表示前i个字符组成的句子，DP的过程需要两层循环，外层循环变量i从1到s.length，表示当前计算的是s的从0到i的子串；内层循环变量j表示子串最后一个单词的长度，从1到i和最大单词长度的较小值。检查单词subString(i-j,i)是否在字典中，dp[i-j]是否非空（非空表示s的从0到j-i的子串合法），若两条同时满足，则将所有合法字符串添加到dp[i]中。
然而上述算法在提交后会有一个s=”aaaaaaaaaaa…b” dict={“a”,”aa”,”aaa”,…} 的测试用例爆内存,解决方法是在执行上述算法前判断s，是否可以由字典中的单词构成。判断过程即139. Word Break的代码。
修改后，实现代码如下：

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        if (!canBreak(s, wordDict)) {
            return new ArrayList<>();
        }
        int len = s.length();
        int maxLen = 0;
        int minLen = Integer.MAX_VALUE;
        Set<String> dict = new HashSet<>();
        for (String string : wordDict) {
            dict.add(string);
            maxLen = Math.max(maxLen, string.length());
            minLen = Math.min(minLen, string.length());
        }
        List<String>[] dp = new ArrayList[len + 1];
        dp[0] = new ArrayList<>();
        dp[0].add("");
        for (int i = 1; i <= len; i++) {
            dp[i] = new ArrayList<>();
            for (int j = minLen; j <= i && j <= maxLen; j++) {
                String sub = s.substring(i - j, i);
                if (dict.contains(sub) && !dp[i - j].isEmpty()) {
                    for (String string : dp[i - j]) {
                        dp[i].add(string + (string == "" ? "" : " ") + sub);
                    }
                }
            }
        }
        return dp[len];
    }

    public boolean canBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        int maxLen = 0;
        for (String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }
        dp[0] = true;
        Set<String> dict = new HashSet<>();
        dict.addAll(wordDict);
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= i && j <= maxLen; j++) {
                if (dp[i - j] && dict.contains(s.substring(i-j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}