以下是 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 数组。

 

更多推荐