Java描述 LeetCode，139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

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

Constraints:

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break

ok，通过题目分析，我们知道这是一个完全背包问题，很符合dp "能不能"的特征，以及物品可以选择很多次。虽然知道了属于什么类型题目，我也想到了先用背包遍历，也想到了状态转移方程，但是遇到了字符串需要对原字符串进行切分去匹配子串。。。dp数组表示后，里面的值怎么填入。。看了答案才明白。具体的看代码吧，以及代码中的几个细节。

public static boolean wordBreak2(String s, List wordDict) {
    Set dict = new HashSet<>(wordDict);
    int n = s.length();

    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    // the out is bag
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            String subStr = s.substring(j, i);
            boolean contains = dict.contains(subStr);
            if (dp[j] && contains) {
                // 这里是dp[i]不是dp[j]，因为更新的是外层背包的状态
                dp[i] = true;
                break;
            } else {
                dp[i] = false;
            }
        }
        System.out.println(Arrays.toString(dp));
    }
    return dp[n];
}

dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0…i-1] 是否能被空格拆分成若干个字典中出现的单词。

第一层循环是背包，也就是原字符串，第二层循环，就是拿着原字符串的各种子串（每次都是[i,j)左开右闭）去字典中匹配。一旦匹配成功了，就要break，不写break的后果，就是会被接下来匹配错误的结果，覆盖掉这个值。第一次先遍历外层背包，出现了很多问题，比起先遍历物品，还是有些区别的。

其他讲解还是看答案吧：https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/