Hard

题目描述

给你两个字符串 s 和 t。

你可以通过从 s 中选择一个子串（可能为空）和从 t 中选择一个子串（可能为空），然后按顺序拼接它们来创建一个新字符串。

返回通过这种方式可以形成的最长回文串的长度。

示例 1：

输入：s = "a", t = "a"
输出：2
解释：从 s 中拼接 "a" 和从 t 中拼接 "a" 得到 "aa"，这是一个长度为 2 的回文串。

示例 2：

输入：s = "abc", t = "def"
输出：1
解释：由于所有字符都不同，最长回文串是任意单个字符，所以答案是 1。

示例 3：

输入：s = "b", t = "aaaa"
输出：4
解释：从 t 中选择 "aaaa" 是最长的回文串，所以答案是 4。

示例 4：

输入：s = "abcde", t = "ecdba"
输出：5
解释：从 s 中拼接 "abc" 和从 t 中拼接 "ba" 得到 "abcba"，这是一个长度为 5 的回文串。

约束条件：

  • 1 <= s.length, t.length <= 1000
  • s 和 t 由小写英文字母组成

提示：

  • 设 dp[i][j] 为以 s[i] 开头和以 t[j] 结尾时的最长答案长度
  • 对于 s，预处理从索引 i 开始的最长回文串长度为 p[i]
  • 对于 t，预处理以索引 j 结尾的最长回文串长度为 q[j]
  • 如果 s[i] != t[j]，那么 dp[i][j] = max(p[i], q[j])
  • 否则，dp[i][j] = max(p[i], q[j], 2 + dp[i + 1][j - 1])

解题思路

这道题需要我们找到通过拼接两个字符串的子串形成的最长回文串。根据题目提示，我们可以使用动态规划的方法。

核心思路：

  1. 预处理阶段：

    • 对于字符串 s，计算从每个位置开始的最长回文子串长度 p[i]
    • 对于字符串 t，计算以每个位置结尾的最长回文子串长度 q[j]

  2. 动态规划阶段：

    • 设 dp[i][j] 表示以 s[i] 开头、t[j] 结尾的拼接回文串的最长长度
    • 状态转移：
      • 如果 s[i] != t[j]：只能选择 s 中从 i 开始的回文或 t 中以 j 结尾的回文，即 dp[i][j] = max(p[i], q[j])
      • 如果 s[i] == t[j]：可以考虑三种情况的最大值：
        • 仅选择 s 中的回文：p[i]
        • 仅选择 t 中的回文：q[j]
        • 将 s[i] 和 t[j] 作为外层，加上中间部分：2 + dp[i+1][j-1]

  3. 边界处理：当索引超出范围时，返回 0。

这种方法充分利用了回文串的性质，通过预处理避免重复计算，时间复杂度为 O(n²m²)，其中 n 和 m 分别是两个字符串的长度。

代码实现

class Solution {
public:
    int longestPalindrome(string s, string t) {
        int n = s.length(), m = t.length();
        
        // 预处理：计算s中从每个位置开始的最长回文长度
        vector<int> p(n, 0);
        for (int i = 0; i < n; i++) {
            // 奇数长度回文
            int l = i, r = i;
            while (l >= 0 && r < n && s[l] == s[r]) {
                p[i] = max(p[i], r - l + 1);
                l--; r++;
            }
            // 偶数长度回文
            l = i; r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) {
                p[i] = max(p[i], r - l + 1);
                l--; r++;
            }
        }
        
        // 预处理：计算t中以每个位置结尾的最长回文长度
        vector<int> q(m, 0);
        for (int j = 0; j < m; j++) {
            // 奇数长度回文
            int l = j, r = j;
            while (l >= 0 && r < m && t[l] == t[r]) {
                q[j] = max(q[j], r - l + 1);
                l--; r++;
            }
            // 偶数长度回文
            l = j - 1; r = j;
            while (l >= 0 && r < m && t[l] == t[r]) {
                q[j] = max(q[j], r - l + 1);
                l--; r++;
            }
        }
        
        // DP
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int result = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                if (s[i] != t[j]) {
                    dp[i][j] = max(p[i], q[j]);
                } else {
                    dp[i][j] = max({p[i], q[j], 2 + dp[i + 1][j - 1]});
                }
                result = max(result, dp[i][j]);
            }
        }
        
        return result;
    }
};

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        
        # 预处理：计算s中从每个位置开始的最长回文长度
        p = [0] * n
        for i in range(n):
            # 奇数长度回文
            l, r = i, i
            while l >= 0 and r < n and s[l] == s[r]:
                p[i] = max(p[i], r - l + 1)
                l -= 1
                r += 1
            # 偶数长度回文
            l, r = i, i + 1
            while l >= 0 and r < n and s[l] == s[r]:
                p[i] = max(p[i], r - l + 1)
                l -= 1
                r += 1
        
        # 预处理：计算t中以每个位置结尾的最长回文长度
        q = [0] * m
        for j in range(m):
            # 奇数长度回文
            l, r = j, j
            while l >= 0 and r < m and t[l] == t[r]:
                q[j] = max(q[j], r - l + 1)
                l -= 1
                r += 1
            # 偶数长度回文
            l, r = j - 1, j
            while l >= 0 and r < m and t[l] == t[r]:
                q[j] = max(q[j], r - l + 1)
                l -= 1
                r += 1
        
        # DP
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        result = 0
        
        for i in range(n - 1, -1, -1):
            for j in range(m):
                if s[i] != t[j]:
                    dp[i][j] = max(p[i], q[j])
                else:
                    dp[i][j] = max(p[i], q[j], 2 + (dp[i + 1][j - 1] if j > 0 else 0))
                result = max(result, dp[i][j])
        
        return result

public class Solution {
    public int LongestPalindrome(string s, string t) {
        int n = s.Length, m = t.Length;
        
        // 预处理：计算s中从每个位置开始的最长回文长度
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            // 奇数长度回文
            int l = i, r = i;
            while (l >= 0 && r < n && s[l] == s[r]) {
                p[i] = Math.Max(p[i], r - l + 1);
                l--; r++;
            }
            // 偶数长度回文
            l = i; r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) {
                p[i] = Math.Max(p[i], r - l + 1);
                l--; r++;
            }
        }
        
        // 预处理：计算t中以每个位置结尾的最长回文长度
        int[] q = new int[m];
        for (int j = 0; j < m; j++) {
            // 奇数长度回文
            int l = j, r = j;
            while (l >= 0 && r < m && t[l] == t[r]) {
                q[j] = Math.Max(q[j], r - l + 1);
                l--; r++;
            }
            // 偶数长度回文
            l = j - 1; r = j;
            while (l >= 0 && r < m && t[l] == t[r]) {
                q[j] = Math.Max(q[j], r - l + 1);
                l--; r++;
            }
        }
        
        // DP
        int[,] dp = new int[n + 1, m + 1];
        int result = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                if (s[i] != t[j]) {
                    dp[i, j] = Math.Max(p[i], q[j]);
                } else {
                    dp[i, j] = Math.Max(Math.Max(p[i], q[j]), 
                                      2 + (j > 0 ? dp[i + 1, j - 1] : 0));
                }
                result = Math.Max(result, dp[i, j]);
            }
        }
        
        return result;
    }
}

var longestPalindrome = function(s, t) {
    const n = s.length, m = t.length;
    
    // 预处理：计算s中从每个位置开始的最长回文长度
    const p = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        // 奇数长度回文
        let l = i, r = i;
        while (l >= 0 && r < n && s[l]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n²m²)
空间复杂度O(nm)

其中 n 和 m 分别是字符串 s 和 t 的长度。预处理阶段需要 O(n² + m²) 时间，动态规划阶段需要 O(nm) 时间。

相关题目