96 lines
2.2 KiB
JavaScript
96 lines
2.2 KiB
JavaScript
/**
|
||
* @param {string} s
|
||
* @param {string[]} wordDict
|
||
* @return {boolean}
|
||
*/
|
||
const wordBreak = function (s, wordDict) {
|
||
|
||
};
|
||
|
||
/*
|
||
使用回溯法，不停的尝试wordict中的单词是否可以构造s
|
||
*/
|
||
function f1(s, wordDict) {
|
||
let result = false;
|
||
const n = s.length;
|
||
|
||
const backtrack = (start) => {
|
||
if (start === n) {
|
||
result = true;
|
||
return;
|
||
}
|
||
|
||
if (result) return; // 剪枝：一旦找到了就不再继续递归
|
||
|
||
for (const word of wordDict) {
|
||
const len = word.length;
|
||
if (start + len > n) continue;
|
||
|
||
let matched = true;
|
||
for (let i = 0; i < len; i++) {
|
||
if (s[start + i] !== word[i]) {
|
||
matched = false;
|
||
break;
|
||
}
|
||
}
|
||
|
||
if (matched) {
|
||
backtrack(start + len);
|
||
}
|
||
}
|
||
};
|
||
|
||
backtrack(0);
|
||
return result;
|
||
}
|
||
|
||
/*
|
||
利用动态规划，定义dp[i]表示s中的前i个字符是否能由wordDict组成，dp[0]=true,前i个字符是否可以由
|
||
wordDict组成，可以从第i个字符开始往前数，如果和wordDict中的某一个字符匹配，并且 dp[i-word.length]==true
|
||
那么 dp[i]===true，由dp[i]的定义可知dp[s.length]表示s的前n个字符（整个字符串）是否可以由wordDict中
|
||
的字符组成
|
||
*/
|
||
function f2(s, wordDict) {
|
||
// 定义dp表，dp[i] 表示s中的前i个字符是否能由wordDict组成
|
||
const dp = Array(s.length + 1).fill(false);
|
||
dp[0] = true;
|
||
for (let i = 1; i < dp.length; i++) {
|
||
// 检测末尾是否匹配
|
||
let cur = i - 1;
|
||
let flag = true;
|
||
for (const word of wordDict) {
|
||
for (let j = word.length - 1; j >= 0; j--, cur--) {
|
||
if (s[cur] !== s[j] || cur < 0) {
|
||
flag = false;
|
||
break;
|
||
}
|
||
}
|
||
if (i >= word.length && flag && dp[i - word.length]) {
|
||
dp[i] = true;
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
return dp[s.length];
|
||
}
|
||
|
||
/*
|
||
f2优化写法
|
||
*/
|
||
function f3(s, wordDict) {
|
||
const dp = 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] && s.slice(i - len, i) === word) {
|
||
dp[i] = true;
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
return dp[s.length];
|
||
}
|