夯实算法-单词拆分

题目：LeetCode

给你一个字符串 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
复制代码

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅有小写英文字母组成
• wordDict 中的所有字符串 互不相同

解题思路

关键的问题是需要回溯，比如某一个某一个子串匹配到了字典中的单词，但下一个子串不匹配，这时可能需要回到上一个匹配，令其匹配字典中的另外一个单词，这样也许就能让后面的找到了匹配，这说明前后的子串是有关系的，用动态规划适合。

状态转移方程

令 f(i) 为字串中到第i个字符时的分割状态，字串长度为 n，那么显然，f(n) 是问题的解。

注意，这里用的依然是个数，0个也即空子串，也是一个状态，因此整体状态的数量是字串长度加1 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n+1</annotation></semantics></math>n+1。

如何求解 f(i) 呢？试想，如果在 i 前面存在一个 j，如果 [j,i] 之间的子串在字典中，那么f(i)=f(j)，也即：

<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo><mo>=</mo><mi>f</mi><mo stretchy="false">(</mo><mi>j</mi><mo stretchy="false">)</mo><mo separator="true">,</mo><mi>i</mi><mi>f</mi><mi>s</mi><mi>u</mi><mi>b</mi><mi>s</mi><mi>t</mi><mi>r</mi><mi>i</mi><mi>n</mi><mi>g</mi><mo stretchy="false">[</mo><mi>i</mi><mo separator="true">,</mo><mi>j</mi><mo stretchy="false">]</mo><mo>∈</mo><mi>w</mi><mi>o</mi><mi>r</mi><mi>d</mi><mi>D</mi><mi>i</mi><mi>c</mi><mi>t</mi></mrow><annotation encoding="application/x-tex">f(i)=f(j),ifsubstring[i,j]∈wordDict</annotation></semantics></math>f(i)=f(j),ifsubstring[i,j]∈wordDict 就是状态转移方程。

初始值，f(0)=truef(0) = truef(0)=true。 因为只有20个，所以用List或者用Set都一样，无太大的差异。

代码实现

public boolean wordBreak(String s, List < String > wordDict) {
    int n = s.length();
    Set < String > dict = wordDict.stream().collect(Collectors.toSet());
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}