拼多多 - 2024/10/19, 腾讯 - 2024/10/17

🌳 题目描述：

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"

🧗难度系数：

⭐️ ⭐️ ⭐

📝思路分析：

根据回文串的定义，回文串满足从中心点(奇数长度：aba, 中心: b, 偶数长度：abba, 中心：bb)向左右扩展, 关于中心点对称的字符都相等。

🌟 方法一：

中心扩展

以字符串中的每个字符-奇数长度/每两个字符-偶数长度为中心向两边扩散，检测最长的回文子串。

💻代码：

Java

 public String longestPalindrome(String s) {
     if (s == null || s.length() == 0) {
         return s;
     }
     int[] index = new int[2];
     for (int i = 0; i < s.length(); i++) {
         // 奇数长度 - 奇偶都不需要额外考虑长度，只需记录左右边界停在哪
         updateLongestPalindromeIfNeeded(i - 1, i + 1, s, index);
         // 偶数长度
         updateLongestPalindromeIfNeeded(i, i + 1, s, index);
     }
     return s.substring(index[0], index[1] + 1);
 }

 private void updateLongestPalindromeIfNeeded(int left, int right, String s, int[] index) {
     if (left < 0 || right >= s.length()) {
         return;
     }
     while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
         left--;
         right++;
     }
     if (right - left - 2 > index[1] - index[0]) {
         index[0] = left + 1;
         index[1] = right - 1;
     }
 }

🚵🏻复杂度分析：

1. 时间复杂度：O(n^2), 每一个点都要扫描两遍字符串，一共有 n 个点。
2. 空间复杂度：O(1)

🌟 方法二：

Manacher's Algorithm

方法一中，对于遍历到的一个新的字符，我们都需要重新计算，而没有用到之前访问过的字符的计算结果，导致时间复杂度过高O(n^2)。而Manacher算法正是利用了之前计算的结果，在线性时间内查找到字符串中最长回文子串，

Manacher算法之所以快，是因为该算法利用了一个回文在另一个更长的回文里的情况，从而能利用之前计算的结果来探索以当前字符为中心的最长回文子串。那么如何利用之前的计算结果：

例如，字符串“abacaba”。当处理到字符“c”时，已经存储了"c"之前每个字母为中心的最长回文。在处理"c"时，算法运行一个循环，确定以"c"为中心的最大回文：“abacaba”。有了这个信息，"c"之后的所有内容看起来都像是"c"之前所有内容的镜像。位于"c"之后的"a"与"c"之前的"a"有相同的最长回文。类似地，"c"之后的"b"的最长回文长度至少等于"c"之前的"b"为中心的最长回文长度，如果它的边界不超出以"c"为中心的边界。再将 "c" 之后的 "b" 运行一个循环判断是否有更长的子串，若有, 则更新右边界。

💻代码：

Java

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        // 预处理字符串, 生成一个奇数长度的字符串
        String str = preprocess(s);
        int n = str.length();

        // 回文子串半径，例 abcba -> 半径为 2 ba
        int[] radius = new int[n];

        int curCenterIndex = 0;
        int rightBound = 0;
        int maxRadius = 0;
        int centerIndex = 0; 

        for (int i = 1; i < n - 1; i++) {
            if (i < rightBound) {
                radius[i] = Math.min(rightBound - i, radius[2 * curCenterIndex - i]);
            }

            // 扩展回文子串
            while (str.charAt(i + 1 + radius[i]) == str.charAt(i - 1 - radius[i])) {
                radius[i]++;
            }

            if (i + radius[i] > rightBound) {
                curCenterIndex = i;
                rightBound = i + radius[i];
            }

            if (radius[i] > maxRadius) {
                maxRadius = radius[i];
                centerIndex = i;
            }
        }

        int start = (centerIndex - maxRadius) / 2;
        return s.substring(start, start + maxRadius);
    }

    private String preprocess(String s) {
        StringBuilder sb = new StringBuilder();
        sb.append('^');
        for (int i = 0; i < s.length(); i++) {
            sb.append('|');
            sb.append(s.charAt(i));
        }
        sb.append("|$");
        return sb.toString();
    }

🚵🏻复杂度分析：

时间复杂度：O(n), 所有扩展回文串的操作将右边界最多移动 n 次, for 循环里的其他操作为常量级，故总的时间复杂度为O(n)。

空间复杂度：O(n), 用于存储所有字符以其为中心的最长回文子串的半径