Skip to main content

单词拆分

Tips

题目类型: Dynamic Programming

背包问题汇总

题目​

给你一个字符串 s 和一个字符串列表 wordDict 作为字典. 如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true.

注意: 不要求字典中出现的单词全部都使用, 并且字典中的单词可以重复使用.

提示:
  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串互不相同
示例
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成.
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成.
     注意, 你可以重复使用字典中的单词.
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

题解​

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const n = s.length
  const dp = new Array(n + 1).fill(false)
  dp[0] = true

  for (let w = 1; w <= n; w++) {
    for (let i = 0; i < w; i++) {
      if (dp[i] && wordDict.includes(s.slice(i, w))) {
        dp[w] = true
        break
      }
    }
  }

  return dp[n]
}