LeetCode 139. 单词拆分（动态规划）—— JavaScript

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

---

题描述：

---

解题思路：

dp[i] 表示从 s[0] 到 s[i -1] 的字符串能否被正确拆分。

dp[i] 通过判断 dp[j] 是为 true 且 [j, i] 的字符串是否存在字典中来求值。

那么我们要求的就是 dp[s.length] 是否能被正确拆分。

---

代码实现：

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

时间复杂度：O(n^2)

空间复杂度：O(n)

本文地址：https://blog.csdn.net/ySFRaabbcc/article/details/111016428