欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode 139. 单词拆分(动态规划)—— JavaScript

程序员文章站 2022-03-20 18:29:20
题链接: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 * @...

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


题描述:

LeetCode 139. 单词拆分(动态规划)—— JavaScript


解题思路:

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];
};

LeetCode 139. 单词拆分(动态规划)—— JavaScript

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

空间复杂度:O(n)

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