单词拆分-139

[sl1673495]

给定一个非空字符串 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

参考：https://leetcode-cn.com/problems/word-break/solution/shou-hui-tu-jie-san-chong-fang-fa-dfs-bfs-dong-tai

这题的动态规划思路不是很好想，

求 s 字符串是否可以由 wordDict 分割，可以转化为从 i = 0 ~ s.length 这个长度为 i 的字符串是否可以由它分割。

而每次对 dp[i] 的求解，可以再定一个变量 j，这个j 从 i ~ 0 遍历，分别把字符串分割为 j ~ i 和 0 ~ j 两部分，

只要：

1. dp[j] 为 true ，说明前 j 个字符已经在动态规划表中确定为可以由 wordDict 分割。
2. j ~ i 这串字符串在 wordDict 中出现，那么结合上一个条件，说明这一整串 0 ~ i 的字符都可以由 wordDict 分割。

那么 dp[i] 的结果也可以确定为 true。

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
let wordBreak = function (s, wordDict) {
  let n = s.length
  if (!n) return true

  let wordSet = new Set(wordDict)
  let dp = []
  dp[0] = true

  for (let i = 0; i <= n; i++) {
    for (let j = i; j >= 0; j--) {
      let word = s.slice(j, i)
      if (wordSet.has(word) && dp[j]) {
        dp[i] = true
        break
      }
    }
  }

  return !!dp[n]
}