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/
题描述:
解题思路:
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