139. 单词拆分

题目

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

说明：

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

题解

动态规划

状态：定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i−1] 是否能被空格拆分成若干个字典中出现的单词

转移方程：dp[i] = dp[j] && check(s[j,...,i-1])

边界条件：dp[0] = true

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