Medium

题目描述

给你两个字符串 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 <= 30
  • s 和 t 由小写英文字母组成。

解题思路

这道题要求我们从两个字符串中分别选择子串进行连接，形成最长的回文串。

暴力枚举法： 由于字符串长度最多为30，我们可以枚举所有可能的子串组合。具体步骤：

  1. 枚举字符串 s 的所有子串（包括空字符串）
  2. 枚举字符串 t 的所有子串（包括空字符串）
  3. 将两个子串连接，检查是否为回文串
  4. 记录最长回文串的长度

优化思路： 我们也可以考虑动态规划或双指针的方法，但由于数据规模较小，暴力枚举已经足够高效。

实现细节：

  • 使用双重循环枚举所有子串组合
  • 对于每个组合，检查连接后的字符串是否为回文
  • 回文检查可以通过双指针从两端向中间比较实现
  • 时间复杂度为 O(n^2 * m^2 * (n+m))，其中 n 和 m 分别是两个字符串的长度

这种方法虽然看似复杂度较高，但在给定的约束条件下（字符串长度≤30）完全可行。

代码实现

class Solution {
public:
    int longestPalindrome(string s, string t) {
        int maxLen = 0;
        int n = s.length(), m = t.length();
        
        // 枚举s的所有子串
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                string sub1 = s.substr(i, j - i);
                
                // 枚举t的所有子串
                for (int x = 0; x <= m; x++) {
                    for (int y = x; y <= m; y++) {
                        string sub2 = t.substr(x, y - x);
                        
                        // 连接两个子串
                        string combined = sub1 + sub2;
                        
                        // 检查是否为回文
                        if (isPalindrome(combined)) {
                            maxLen = max(maxLen, (int)combined.length());
                        }
                    }
                }
            }
        }
        
        return maxLen;
    }
    
private:
    bool isPalindrome(const string& str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str[left] != str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        def is_palindrome(string):
            return string == string[::-1]
        
        max_len = 0
        n, m = len(s), len(t)
        
        # 枚举s的所有子串
        for i in range(n + 1):
            for j in range(i, n + 1):
                sub1 = s[i:j]
                
                # 枚举t的所有子串
                for x in range(m + 1):
                    for y in range(x, m + 1):
                        sub2 = t[x:y]
                        
                        # 连接两个子串并检查是否为回文
                        combined = sub1 + sub2
                        if is_palindrome(combined):
                            max_len = max(max_len, len(combined))
        
        return max_len

public class Solution {
    public int LongestPalindrome(string s, string t) {
        int maxLen = 0;
        int n = s.Length, m = t.Length;
        
        // 枚举s的所有子串
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                string sub1 = s.Substring(i, j - i);
                
                // 枚举t的所有子串
                for (int x = 0; x <= m; x++) {
                    for (int y = x; y <= m; y++) {
                        string sub2 = t.Substring(x, y - x);
                        
                        // 连接两个子串
                        string combined = sub1 + sub2;
                        
                        // 检查是否为回文
                        if (IsPalindrome(combined)) {
                            maxLen = Math.Max(maxLen, combined.Length);
                        }
                    }
                }
            }
        }
        
        return maxLen;
    }
    
    private bool IsPalindrome(string str) {
        int left = 0, right = str.Length - 1;
        while (left < right) {
            if (str[left] != str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
}

var longestPalindrome = function(s, t) {
    function isPalindrome(str) {
        let left = 0, right = str.length - 1;
        while (left < right) {
            if (str[left] !== str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    
    let maxLen = 0;
    const n = s.length, m = t.length;
    
    // 枚举s的所有子串
    for (let i = 0; i <= n; i++) {
        for (let j = i; j <= n; j++) {
            const sub1 = s.substring(i, j);
            
            // 枚举t的所有子串
            for (let x = 0; x <= m; x++) {
                for (let y = x; y <= m; y++) {
                    const sub2 = t.substring(x, y);
                    
                    // 连接两个子串并检查是否为回文
                    const combined = sub1 + sub2;
                    if (isPalindrome(combined)) {
                        maxLen = Math.max(maxLen, combined.length);
                    }
                }
            }
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n² × m² × (n+m))
空间复杂度O(n+m)

其中 n 和 m 分别是字符串 s 和 t 的长度。时间复杂度中，O(n² × m²) 用于枚举所有子串组合，O(n+m) 用于回文检查。空间复杂度主要用于存储临时的连接字符串。