给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

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

解法1 – Bottom-up

这道题我们使用动态规划来解决，给定字符串s，声明类型为boolean的数组dp[|s| + 1]。dp[i] = true时表示长度为i的字符串能够被拆分为一个或多个在字典中出现的单词，因为这句话太长了，下文简称为“可构成的”。

在填充dp数组时，我们首先变化的是问题规模，即字符串s的前缀长度len。对于长度为len的字符串，我们设置分割点splitIdx，可以写出状态转移公式dp[len] = dp[splitIdx] && s[splitIdx...len) in wordDict，其中splitIdx<len，初始dp[0] = true，表示空串是可构成的。公式的物理意义为如果字符串s的前splitIdx个字符组成的子串s[0…splitIdx)是可构成的(即dp[splitIdx] = true)，且s[splitIdx…len)在字典中存在，那么s[0…len)就是“可构成的”。我们不断地增加问题规模（也就是len）并填充dp数组，当len与s长度相同我们就得到了问题的解。

举个例子s = “leetcode”，dp[|s|+1] = dp[9]，初始化dp[0] = true，wordDict = {“leet”, “code”}。首先dp[4]=true，因为dp[0] = true, s[0…4) = “leet” in wordDict；dp[8] = true，因为dp[4] && s[4…8) in wordDict。那么最后答案存储在dp[|s|]即dp[8]中值为true，所以leetcode是可构成的。

在实现时，我们将wordDict从List转换为HashSet，这样才能够迅速地查找单词是否存在。时间复杂度为O(n^3)，因为双层循环是O(n^2)，但是内部有substring操作；空间复杂度为O(n)。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        Set<String> wordSet = new HashSet<>(wordDict);

        dp[0] = true;
        for (int len = 1; len <= s.length(); len++) {
            for (int splitIdx = 0; splitIdx < len; splitIdx++) {
                if (dp[splitIdx] && wordSet.contains(s.substring(splitIdx, len))) {
                    dp[len] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

解法2 – Top-down

解法1采用Bottom-up的角度解决问题，较为难以理解。解法2从Top-down的角度解决问题，例如s = “leetcode”，要判断“leetcode”是否可分割，我们要判断：

• “”可分割且“leetcode”在字典中，或者
• “l”可分割且“eetcode”在字典中，或者
• “le”可分割且“eetcode”在字典中，或者
• “lee”可分割且“tcode”在字典中，或者
• ……
• “leetcod”可分割且“e”在字典中

那么要判断“lee”是否可分割：

• “”可分割且“lee”在字典中，或者
• “l”可分割且“ee”在字典中，或者
• “le”可分割且“e”在字典中

对“lee”的求解又是一个子问题，可以按照相同的模式来解决。这明显是一种递归的形式，我们可以使用递归来求解。我们观察到，上述过程存在相同的子问题被重复求解，因此我们可以使用Map<String, Boolean> cache来记录求解过的子问题，避免重复计算。cache需要被初始化，将<“”, true>放入其中。

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

    public boolean wordBreak(String s, List<String> wordDict) {
        cache.put("", true);
        return wordBreak(s, new HashSet<>(wordDict));
    }

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

        for (int i = 0; i < s.length(); i++) {
            if (wordBreak(s.substring(0, i), wordSet) && wordSet.contains(s.substring(i))) {
                cached = true;
                break;
            }
        }
        // 如果单词不可分割，那么为false
        if (cached == null)
            cached = false;
        cache.put(s, cached);
        return cached;
    }
}