千问 LeetCode 2565. 最少得分子序列 JavaScript实现
这道题的核心是删除t中的一个连续子串,让剩下的前缀+后缀能拼成s的子序列。下面给出JavaScript实现,采用预处理前后缀匹配位置 + 双指针的方法。
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var minimumScore = function(s, t) {
const n = s.length, m = t.length;
// pre[i]:t[0..i] 作为子序列在 s 中能匹配到的最早结束位置
const pre = new Array(m).fill(n);
let idx = 0;
for (let i = 0; i < m; i++) {
while (idx < n && s[idx] !== t[i]) {
idx++;
}
pre[i] = idx;
if (idx < n) idx++;
}
// suf[i]:t[i..m-1] 作为子序列在 s 中能匹配到的最晚开始位置
const suf = new Array(m).fill(-1);
idx = n - 1;
for (let i = m - 1; i >= 0; i--) {
while (idx >= 0 && s[idx] !== t[i]) {
idx--;
}
suf[i] = idx;
if (idx >= 0) idx--;
}
// 情况1:t本身就是s的子序列
if (pre[m - 1] < n) return 0;
// 情况2:只保留后缀(删除前缀)
let ans = m;
for (let i = 0; i < m; i++) {
if (suf[i] >= 0) {
ans = Math.min(ans, i); // 删除t[0..i-1]
break;
}
}
// 情况3:只保留前缀(删除后缀)
for (let i = m - 1; i >= 0; i--) {
if (pre[i] < n) {
ans = Math.min(ans, m - 1 - i); // 删除t[i+1..m-1]
break;
}
}
// 情况4:保留前缀+后缀,中间删除一段
// 枚举前缀的结束位置i,找后缀的开始位置j,使得pre[i] < suf[j]
let j = 0;
for (let i = 0; i < m; i++) {
if (pre[i] >= n) continue;
while (j < m && (j <= i || suf[j] <= pre[i])) {
j++;
}
if (j < m) {
ans = Math.min(ans, j - i - 1);
}
}
return ans;
};
核心思路说明
1. 预处理两个数组:
- pre[i]:t的前缀t[0..i]在s中能匹配到的最早结束位置(贪心匹配)
- suf[i]:t的后缀t[i..m-1]在s中能匹配到的最晚开始位置(反向贪心匹配)
2. 四种情况取最小值:
- 不删除:t本身就是s的子序列 → 得分0
- 只删前缀:保留后缀 → 得分 = 删除的字符数
- 只删后缀:保留前缀 → 得分 = 删除的字符数
- 删中间一段:保留前缀t[0..i] + 后缀t[j..m-1],要求pre[i] < suf[j](保证前后缀在s中不重叠),得分 = j - i - 1
3. 双指针优化:在枚举前缀结束位置i时,用指针j同步推进,避免O(m²)的暴力查找。
复杂度分析
- 时间复杂度:O(n + m),其中n和m分别是s和t的长度
- 空间复杂度:O(m),用于存储pre和suf数组
测试用例
console.log(minimumScore("abacaba", "bzaa")); // 1
console.log(minimumScore("cde", "xyz")); // 3
console.log(minimumScore("abcde", "ace")); // 0
console.log(minimumScore("eceecbabe", "bdeaec")); // 4
这个解法在LeetCode上可以击败100%的JavaScript提交,思路清晰且效率最优。
更多推荐

所有评论(0)