20200722-139.word-break.md

#139.word-break

题目链接：https://leetcode-cn.com/problems/word-break/

参考链接：https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/

题目

给定一个非空字符串 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]动态规划

• 使用数组dp记录第i个长度前的字符串能否由字典中的字符串拆分
• 当前长度i能否由数组拆分，取决于，目标字符串前j长度是否能被分割和由j到i的长度是否在字典中，即s.slice(j, i)是否在字典中。
• 这样就把问题分为两个部分，因为j < i，所以前一部分已经在之前计算过了，所以每次只需要判断后一部分即可

代码

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
  let dp = [];
  dp[0] = true;
  for(let i = 1; i <= s.length; i++){
    dp[i] = false;
    for(let j = 0; j < i; j++){
      if(dp[j] && wordDict.includes(s.slice(j, i))){
        dp[i] = true
      }
    }
  }
  return dp[s.length]
};

思路[2]动态规划优化

• 对动态规划思路的一种优化
• 还是分为两部分，只不过后半部分的选择做了变化。
• 因为总是需要与字典中的字符串比较，所以只需要判断字典中的字符串即可，不需要全部截取，所以就从原先的从j = 0 到 j < i变为字典的长度。
• 此时如果当前长度比字典中要判断的字符串长度小，则跳过
• 然后在s中从末尾剪切出与字典中要判断的字符串长度相同的子串，判断子串与字符串是否相等，如果不相等则跳过
• 如果相等，再判断字符串前半部分是否可分割，此处与动态规划思路相同，
• 如果包含一个可分割则代表当前长度可分割，则进行下一个长度的判断

代码

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
  let dp = [];
  dp[0] = true;
  for(let i = 1; i <= s.length; i++){
    dp[i] = false;
    for(let j = 0; j < wordDict.length; j++){
      const item = wordDict[j];
      // 当前i的长度要比判断长度大，才需要判断相等，且标示前半部分的字符串下标
      const prevLength = i - item.length;
      if(prevLength >= 0 && item === s.slice(prevLength, i) && dp[prevLength]){
        // 如果当前字符计算过则不再计算，
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length]
};

思路[3]暴力法

• 把暴力递归每个字符串长度，进行判断是否包含
• 这个方法超出时间限制

代码

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */

var helper = function(s, index, wordDict){
  if(index === s.length){
    return true
  }
  for(let i = index; i < s.length; i++){
    let parent = s.slice(index, i+1);
    if(wordDict.includes(parent)){
      let res = helper(s, i+1, wordDict);
      if(res){
        return true
      }
    }
  }
  return false
}

var wordBreak = function(s, wordDict) {
  let result = helper(s, 0, wordDict);
  return result
};

思路[4]暴力法优化

• 此处是对暴力法的优化，一共做了三处优化
• 将原先遍历截取字符串，变为遍历字典长度，因为需要比较的就是字典中的字符串，所以不用全部截取，然后查看
• 将字典提前按照长度排序，这样做的好处是，先从长的进行判断，如果字典中出现重复字符串，或者包含字符串，这样就优先匹配长字符串，减少遍历次数
• 使用set缓存处理过的字符串，去除重复的处理，因为每次都是在上次的基础上进行再次的截取，最后几位如果截取相同，说明之前截取到了长串包含短串的情况，所以要跳过执行

代码

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var helper = function(s, wordDict, set){
  if(s === '') return true;
  for(let word of wordDict){
    if(s.indexOf(word) === 0){
      let wd = s.slice(word.length);
      if(!set.has(wd)){
        let res = helper(wd, wordDict, set);
        set.add(wd);
        if(res) return true;
      }
    }
  }
  return false
}

var wordBreak = function(s, wordDict) {
  wordDict.sort((a, b) => b.length - a.length);
  let set = new Set()
  return helper(s, wordDict, set)
};

思考

• 暴力法还是要从减少执行次数进行优化
• 动态规划原来的理解是找上次的关系，现在看来是找和以前执行过的步骤的关系，不只是上次的执行
• 动态规划的优化也是一样，优化执行次数