最长回文子串

难度中等5093收藏分享切换为英文接收动态反馈
给你一个字符串 s，找到 s 中最长的回文子串。

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

方法一：暴力解法
根据回文子串的定义，枚举所有长度大于等于 22 的子串，依次判断它们是否是回文；
可以只针对大于「当前得到的最长回文子串长度」的子串进行回文验证；
当得到了一个更长的回文时，不需要真的做截取。只需要记录「当前子串的起始位置」和「子串长度」。

  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.         // s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组
  12.         char[] charArray = s.toCharArray();
  14.         // 枚举所有长度大于 1 的子串 charArray[i..j]
  15.         for (int i = 0; i < len - 1; i++) {
  16.             for (int j = i + 1; j < len; j++) {
  17.                 if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
  18.                     maxLen = j - i + 1;
  19.                     begin = i;
  20.                 }
  21.             }
  22.         }
  23.         return s.substring(begin, begin + maxLen);
  24.     }
  26.     /**
  27.      * 验证子串 s[left..right] 是否为回文串
  28.      */
  29.     private boolean validPalindromic(char[] charArray, int left, int right) {
  30.         while (left < right) {
  31.             if (charArray[left] != charArray[right]) {
  32.                 return false;
  33.             }
  34.             left++;
  35.             right--;
  36.         }
  37.         return true;
  38.     }
  39. }

复杂度分析：

时间复杂度：O(N^3)O(N
3
)，这里 NN 是字符串的长度，枚举字符串的左边界、右边界，然后继续验证子串是否是回文子串，都与 NN 相关；
空间复杂度：O(1)O(1)，只使用到常数个临时变量，与字符串长度无关。
方法二：动态规划
回文天然具有「状态转移」性质：一个长度严格大于 22 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。「动态规划」的方法根据这样的性质得到。

第 1 步：定义状态
dp[i][j] 表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。

第 2 步：思考状态转移方程
根据头尾字符是否相等，需要分类讨论：

dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
说明：

「动态规划」的「自底向上」求解问题的思路，很多时候是在填写一张二维表格。由于 s[i..j] 表示 s 的一个子串，因此 i 和 j 的关系是 i <= j，只需要填这张表格对角线以上的部分；
看到 dp[i + 1][j - 1] 就需要考虑特殊情况：如果去掉 s[i..j] 头尾两个字符子串 s[i + 1..j - 1] 的长度严格小于 22（不构成区间），即 j - 1 - (i + 1) + 1 < 2j−1−(i+1)+1<2 时，整理得 j - i < 3j−i<3，此时 s[i..j] 是否是回文只取决于 s[i] 与 s[j] 是否相等。结论也比较直观：j - i < 3j−i<3 等价于 j - i + 1 < 4j−i+1<4，即当子串 s[i..j]s[i..j] 的长度等于 22 或者等于 33 的时候，s[i..j] 是否是回文由 s[i] 与 s[j] 是否相等决定。
第 3 步：考虑初始化
单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true。根据第 2 步的说明：当 s[i..j] 的长度为 22 时，只需要判断 s[i] 是否等于 s[j]，所以二维表格对角线上的数值不会被参考。所以不设置 dp[i][i] = true 也能得到正确结论。

第 4 步：考虑输出
一旦得到 dp[i][j] = true，就记录子串的「长度」和「起始位置」。没有必要截取，这是因为截取字符串也有性能消耗。

第 5 步：考虑优化空间
下面给出的「参考代码」，在填表的过程中，只参考了左下方的数值。事实上可以优化，但是增加了代码编写和理解的难度，丢失了可读性和可解释性。在这里不做优化空间；
填表应该遵守这样的原则：总是先得到小子串是否是回文的结果，然后大子串才能参考小子串的判断结果，所以填表顺序很重要；
建议自己动手，画一下表格，相信会对「动态规划」作为一种「表格法」有更好的理解。

  1. public class Solution {
  3.     public String longestPalindrome(String s) {
  4.         // 特殊用例判断
  5.         int len = s.length();
  6.         if (len < 2) {
  7.             return s;
  8.         }
  10.         int maxLen = 1;
  11.         int begin = 0;
  13.         // dp[i][j] 表示 s[i, j] 是否是回文串
  14.         boolean[][] dp = new boolean[len][len];
  15.         char[] charArray = s.toCharArray();
  17.         for (int i = 0; i < len; i++) {
  18.             dp[i][i] = true;
  19.         }
  20.         for (int j = 1; j < len; j++) {
  21.             for (int i = 0; i < j; i++) {
  22.                 if (charArray[i] != charArray[j]) {
  23.                     dp[i][j] = false;
  24.                 } else {
  25.                     if (j - i < 3) {
  26.                         dp[i][j] = true;
  27.                     } else {
  28.                         dp[i][j] = dp[i + 1][j - 1];
  29.                     }
  30.                 }
  32.                 // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
  33.                 if (dp[i][j] && j - i + 1 > maxLen) {
  34.                     maxLen = j - i + 1;
  35.                     begin = i;
  36.                 }
  37.             }
  38.         }
  39.         return s.substring(begin, begin + maxLen);
  40.     }
  41. }

复杂度分析：

时间复杂度：O(N^{2})O(N
2
)，这里 NN 是字符串的长度；
空间复杂度：O(N^{2})O(N
2
)，使用了一张二维表格记录所有可能的情况，因此空间复杂度是 O(N^{2})O(N
2
)。
「暴力法」和「动态规划」枚举了字符串的左右边界，我们还可以 枚举可能出现的回文子串的「中心位置」，从「中心位置」尝试尽可能向两边，得到回文串。

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         if (s == null || s.length() < 1) {
  4.             return "";
  5.         }
  6.         int start = 0, end = 0;
  7.         for (int i = 0; i < s.length(); i++) {
  8.             int len1 = expandAroundCenter(s, i, i);
  9.             int len2 = expandAroundCenter(s, i, i + 1);
  10.             int len = Math.max(len1, len2);
  11.             if (len > end - start) {
  12.                 start = i - (len - 1) / 2;
  13.                 end = i + len / 2;
  14.             }
  15.         }
  16.         return s.substring(start, end + 1);
  17.     }
  19.     public int expandAroundCenter(String s, int left, int right) {
  20.         while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
  21.             --left;
  22.             ++right;
  23.         }
  24.         return right - left - 1;
  25.     }
  26. }

复杂度分析

时间复杂度：O(n^2)O(n
2
)，其中 nn 是字符串的长度。长度为 11 和 22 的回文中心分别有 nn 和 n-1n−1 个，每个回文中心最多会向外扩展 O(n)O(n) 次。

其他精简代码收集:
1650384616(1).png

  2. public String longestPalindrome1(String s) {
  4.         if (s == null || s.length() == 0) {
  5.             return "";
  6.         }
  7.         int strLen = s.length();
  8.         int left = 0;
  9.         int right = 0;
  10.         int len = 1;
  11.         int maxStart = 0;
  12.         int maxLen = 0;
  14.         for (int i = 0; i < strLen; i++) {
  15.             left = i - 1;
  16.             right = i + 1;
  17.             while (left >= 0 && s.charAt(left) == s.charAt(i)) {
  18.                 len++;
  19.                 left--;
  20.             }
  21.             while (right < strLen && s.charAt(right) == s.charAt(i)) {
  22.                 len++;
  23.                 right++;
  24.             }
  25.             while (left >= 0 && right < strLen && s.charAt(right) == s.charAt(left)) {
  26.                 len = len + 2;
  27.                 left--;
  28.                 right++;
  29.             }
  30.             if (len > maxLen) {
  31.                 maxLen = len;
  32.                 maxStart = left;
  33.             }
  34.             len = 1;
  35.         }
  36.         return s.substring(maxStart + 1, maxStart + maxLen + 1);
  38.     }
  1. public String longestPalindrome(String s) {
  2.         if (s == null || s.length() < 2) {
  3.             return s;
  4.         }
  5.         int strLen = s.length();
  6.         int maxStart = 0;  //最长回文串的起点
  7.         int maxEnd = 0;    //最长回文串的终点
  8.         int maxLen = 1;  //最长回文串的长度
  10.         boolean[][] dp = new boolean[strLen][strLen];
  12.         for (int r = 1; r < strLen; r++) {
  13.             for (int l = 0; l < r; l++) {
  14.                 if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
  15.                     dp[l][r] = true;
  16.                     if (r - l + 1 > maxLen) {
  17.                         maxLen = r - l + 1;
  18.                         maxStart = l;
  19.                         maxEnd = r;
  21.                     }
  22.                 }
  24.             }
  26.         }
  27.         return s.substring(maxStart, maxEnd + 1);
  29.     }
  30. }