Kimi LeetCode 3504. 子字符串连接后的最长回文串 II JavaScript实现
以下是 LeetCode 3504「子字符串连接后的最长回文串 II」的 JavaScript 实现:
解题思路
与 Rust 版本相同的算法:中心扩散 + 动态规划:
1. 预处理回文数组:对每个字符串,用中心扩散法计算 `g[i]`,表示从位置 `i` 开始的最长回文子串长度。
2. 反转 t:将 `t` 反转后,问题转化为找 `s` 的前缀和反转后 `t` 的前缀的最长公共子串(这样拼接后自然对称)。
3. DP 匹配:`f[i][j]` 表示以 `s[i-1]` 和 `t[j-1]` 结尾的最长匹配长度。当 `s[i-1] == t[j-1]` 时,`f[i][j] = f[i-1][j-1] + 1`。
4. 更新答案:匹配部分贡献 `f[i][j] * 2` 的长度,还可以在 `s` 或 `t` 的剩余部分附加一个回文。
JavaScript 代码
```javascript
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var longestPalindrome = function(s, t) {
// 反转 t
const tRev = t.split('').reverse().join('');
const m = s.length;
const n = tRev.length;
// g1[i] = 从 s[i] 开始的最长回文子串长度
const g1 = calc(s);
// g2[i] = 从 tRev[i] 开始的最长回文子串长度
const g2 = calc(tRev);
// 答案至少可以是 s 或 t 中单独的最长回文子串
let ans = Math.max(...g1, ...g2);
// f[i][j] = 以 s[i-1] 和 tRev[j-1] 结尾的最长匹配长度
const f = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s[i - 1] === tRev[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
// 匹配部分 + s 剩余部分的回文
const extraS = (i < m) ? g1[i] : 0;
ans = Math.max(ans, f[i][j] * 2 + extraS);
// 匹配部分 + t 剩余部分的回文
const extraT = (j < n) ? g2[j] : 0;
ans = Math.max(ans, f[i][j] * 2 + extraT);
}
}
}
return ans;
};
/**
* 中心扩散,计算从每个位置开始的最长回文子串长度
* @param {string} s
* @return {number[]}
*/
function calc(s) {
const n = s.length;
const g = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
expand(s, g, i, i); // 奇数长度
expand(s, g, i, i + 1); // 偶数长度
}
return g;
}
/**
* 中心扩散辅助函数
* @param {string} s
* @param {number[]} g
* @param {number} l
* @param {number} r
*/
function expand(s, g, l, r) {
const n = s.length;
while (l >= 0 && r < n && s[l] === s[r]) {
g[l] = Math.max(g[l], r - l + 1);
l--;
r++;
}
}
```
复杂度
- 时间复杂度:O(m \times (m + n)),其中 m, n 分别为 `s` 和 `t` 的长度。
- 空间复杂度:O(m \times n),用于 DP 数组。
更多推荐



所有评论(0)