题目描述

解题思路

dp

• 确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

• 确定递推公式

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
表示截取的上一个字符串已经能被拆分，且在这个区间也出现在字典中，此时才满足0~i能被拆分。

• 初始化

从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]一定要为true，否则递归下去后面都都是false了。
那么dp[0]有没有意义呢？
dp[0]表示如果字符串为空的话，说明出现在字典里。

• 确定遍历顺序

题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。本题不是组合也不是排序，所以先遍历什么都可以。
那么本题使用求排列的方式，还是求组合的方式都可以。
即：外层for循环遍历物品，内层for遍历背包 或者 外层for遍历背包，内层for循环遍历物品 都是可以的。
但本题还有特殊性，因为是要求子串，最好是遍历背包放在外循环，将遍历物品放在内循环。
如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的子串都预先放在一个容器里。

• 举例推导dp[i]

以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例，dp状态如图：

public boolean wordBreak(String s, List<String> wordDict) {
    // dp数组表示i的背包容量是否可以拆分出单词，dp[i]表示是否
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {  // 先遍历背包
        for (int j = 0; j < i; j++) {
            String str = s.substring(j, i);
            if (wordDict.contains(str) && dp[j] != false) { // 当以前的串可以拆分，并且包含此单词
                dp[i] = true;
            }
        }
    }
    return dp[s.length()];
}

回溯法

采用记忆回溯法

/**
         * 回溯法
         *
         * @param s
         * @param wordDict
         * @return
         */
public boolean wordBreak(String s, List<String> wordDict) {
    set = new HashSet<>(wordDict);
    memo = new int[s.length()];
    return traversal(s, 0);
}
private Set<String> set;
private int[] memo; // 用来标记startIndex是否被选择过（-1表示从startIndex开始选择不满足）
public boolean traversal(String s, int startIndex) {
    // 是否选择到边界
    if (startIndex >= s.length()) {
        return true;
    }
    // 如果被选择过，直接返回结果
    if (memo[startIndex] == -1) {
        return false;
    }
    for (int i = startIndex; i < s.length(); i++) {
        String str = s.substring(startIndex, i + 1);
        // 如果单词在字典中，且递归后边的都返回true，则此时字符串满足
        if (set.contains(str) && traversal(s, i + 1)) {
            return true;
        }
    }
    // 标记
    memo[startIndex] = -1;
    return false;
}