139. Word Break

Leetcode link

题目简介

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

题目给我们一个字符串 s 以及一个字符串数组 wordDict

要求我们判断是否可以从 wordDict 中取出字符串 word 拼成 s

wordDict 中的字符串可以重复使用，但是不允许拆开

解题思路

我们先从字符串 s 入手，假设有 s = 'leetcode' ，且 wordDict 中的字符串可以拼成 s，我们有两种可能性需要讨论：

1. wordDict = ['leetcode']，代表 wordDict 中的一个字符串等于 s
2. wordDict = ['leet', 'code']，代表 wordDict 中的多个字符串加起来可以拼出 s

第一种情况很直觉，我们重点看第二种情况要怎么判断

首先我们需要遍历字符串 s，目的是判断每一个 s[0..i] 子字符串是否可以找到对应的 word

判断条件有三：

1. i >= word.length：子字符串必须要大于 word，否则不能比较
2. s.substring(i-word.length+1, i+1) === word：我们要选出 s 字符串中等于 word 的子字符串与 word 比较
3. s[0...i-word.length] 这个子字符串必须已经能被其他 word 拼起来

为了判断第三点条件，我们需要使用 dp 的思路：

1. 声明一个 dp 数组，长度为 s.length+1，默认赋值 false
2. 设置 dp[0] = true 代表当字符串 s 长度为 0 的时候，结果是 true
3. 遍历 s 中的子字符串，对每个子字符串遍历 wordDict 中的 word
4. 如果有 i 满足以上三个条件，设置 dp[i] = true
5. 最后返回 dp[s.length]

Javascript

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

    for (let i = 1; i <= s.length; i++) {
        for (const word of wordDict) {
            const len = word.length
            if (i >= len && dp[i - len] && word === s.substring(i - len, i)) {
                dp[i] = true
                break;
            }
        }
    }

    return dp[s.length]
};