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

示例 1:
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2:
输入：s = “cbbd”
输出：“bb”

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

本题无思路，所以看了题解，接下来介绍三种方法。

1. 暴力解法

从字符串的s[0]开始，依次递增长度，判断每个字符串是否为回文串。一共三层循环，时间复杂度为O(n3)。

  1. public boolean isPalindromic(String s) {
  2.         int len = s.length();
  3.         for (int i = 0; i < len / 2; i++) {
  4.             if (s.charAt(i) != s.charAt(len - i - 1)) {
  5.                 return false;
  6.             }
  7.         }
  8.         return true;
  9.     }
  10. // 暴力解法
  11. public String longestPalindrome(String s) {
  12.     String ans = "";
  13.     int max = 0;
  14.     int len = s.length();
  15.     for (int i = 0; i < len; i++)
  16.         for (int j = i + 1; j <= len; j++) {
  17.             String test = s.substring(i, j);
  18.             if (isPalindromic(test) && test.length() > max) {
  19.                 ans = s.substring(i, j);
  20.                 max = Math.max(max, ans.length());
  21.             }
  22.         }
  23.     return ans;
  24. }

2. 动态规划法

因为对于一个回文串(长度大于2)，将其首尾去掉之后，也必定是回文串。
我们用 P(i,j) 表示字符串 s 的第 i 到 j 个字母组成的串（下文表示成 s[i:j]）是否为回文串：
image.png
这里的「其它情况」包含两种可能性：
s[i, j] 本身不是一个回文串；
i > j，此时 s[i, j] 本身不合法。
那么我们就可以写出动态规划的状态转移方程：
image.png
也就是说，只有 s[i+1:j-1] 是回文串，并且 s 的第 i 和 j 个字母相同时，s[i:j] 才会是回文串。对于长度小于2的子串，当长度为1时，显然是回文串，当长度为2时，首尾两字符相同即为回文串。根据这个思路，我们就可以完成动态规划了，最终的答案即为所有 P(i, j) =true 中 j-i+1（即子串长度）的最大值。注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。时间复杂度为O(n2)。

  1. public class Solution {
  3.     public String longestPalindrome(String s) {
  4.         int len = s.length();
  5.         if (len < 2) {
  6.             return s;
  7.         }
  9.         int maxLen = 1;
  10.         int begin = 0;
  11.         // dp[i][j] 表示 s[i..j] 是否是回文串
  12.         boolean[][] dp = new boolean[len][len];
  13.         // 初始化：所有长度为 1 的子串都是回文串
  14.         for (int i = 0; i < len; i++) {
  15.             dp[i][i] = true;
  16.         }
  18.         char[] charArray = s.toCharArray();
  19.         // 递推开始
  20.         // 先枚举子串长度
  21.         for (int L = 2; L <= len; L++) {
  22.             // 枚举左边界，左边界的上限设置可以宽松一些
  23.             for (int i = 0; i < len; i++) {
  24.                 // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
  25.                 int j = L + i - 1;
  26.                 // 如果右边界越界，就可以退出当前循环
  27.                 if (j >= len) {
  28.                     break;
  29.                 }
  31.                 if (charArray[i] != charArray[j]) {
  32.                     dp[i][j] = false;
  33.                 } else {
  34.                     // 对于长度为3的子串，只要首尾字符相同，也是回文串
  35.                     if (j - i < 3) {
  36.                         dp[i][j] = true;
  37.                     } else {
  38.                         dp[i][j] = dp[i + 1][j - 1];
  39.                     }
  40.                 }
  42.                 // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
  43.                 if (dp[i][j] && j - i + 1 > maxLen) {
  44.                     maxLen = j - i + 1;
  45.                     begin = i;
  46.                 }
  47.             }
  48.         }
  49.         return s.substring(begin, begin + maxLen);
  50.     }
  51. }

3. 中心扩展法

我们知道回文串一定是对称的，所以我们可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。由于存在奇数的字符串和偶数的字符串，所以我们需要从一个字符开始扩展，或者从两个字符之间开始扩展，所以总共有 n+n-1 个中心。时间复杂度为O(n2)。

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    // 遍历每个位置，当做中心位
    for (int i = 0; i < s.length(); i++) {
        // 分别拿到奇数偶数的回文子串长度
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        // 对比最大的长度
        int len = Math.max(len1, len2);
        // 计算对应最大回文子串的起点和终点
        // start=i-(len-1)/2，这里len-1是考虑到奇偶两种长度的子串
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    // 这里的end+1是因为java自带的左闭右开的原因
    return s.substring(start, end + 1);
}
    /**
     *
     * @param s             输入的字符串
     * @param left          起始的左边界
     * @param right         起始的右边界
     * @return              回文串的长度
     */
    private int expandCenter(String s,int left,int right){
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        // 跳出循环的时候恰好满足 s.charAt(left) ！= s.charAt(right)
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        // 回文串的长度是right-left+1-2 = right - left - 1
        // 因为在结束循环时left--，right--
        return right - left - 1;
    }