image.png

思路

做的时候一直在想01背包里的 474.一和零，还以为也是同样的加维度做法。然鹅并不是！
474题中，是统计0和1的个数，而这道题的字符串是固定的字符哈。
不会做，看解析了。

完全背包做法

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词，说明就是一个完全背包！

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

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

  1. 确定递推公式⭐

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

  1. 遍历顺序⭐

先遍历物品再遍历背包的方法我写不出来T-T
只能先这么理解：单词的组合是有顺序的，所以按照排序的遍历方法来做。

  1. var wordBreak = function(s, wordDict) {
  2.     let dp =new Array(s.length+1).fill(false)
  3.     dp[0] =true
  4.     // 背包在外，物品在内
  5.     for(let j=0;j<=s.length;j++){
  6.         for(let i=0;i<wordDict.length;i++){
  7.             if(j>=wordDict[i].length){
  8.                 if(dp[j-wordDict[i].length] && (s.slice(j-wordDict[i].length,j)===wordDict[i])){
  9.                     dp[j] =true
  10.                 }
  11.             }
  12.         }
  13.     }
  15.     return dp[s.length]
  16. };

回溯+记忆化搜索

 // 回溯法+记忆化搜索
    let arr = [];
    const dfs = (start) => {
        if(start === s.length) return true;
        if(arr[start] !== undefined) return arr[start]; 
        let res = false;

        for(let word of wordDict) {
            if(s.startsWith(word, start)) {
                res = res || dfs(start + word.length);
                arr[start + word.length] = res;
            }
        }

        return res;
    }

    return dfs(0);

startsWith（）

ES6新增方法
startsWith() 方法用于检测字符串是否以指定的子字符串开始。
如果是以指定的子字符串开头返回 true，否则 false。
string.startsWith(searchvalue, start）