0139. 单词拆分.md

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。

来源：力扣（LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

暴力解，会超时

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
  var helper = (str) => {
    if (wordDict.some(i => i === str)) return true
    else {
      return wordDict.filter(i => str.indexOf(i) === 0).some(o => helper(str.substring(o.length)))
    }
  }

  return helper(s)
};

动态规划，注意 i, j 边界条件

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