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

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

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

示例 3：
输入：s = “a”
输出：”a”

示例4：
输入： s = “ac”
输出：”a”

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成

方法一：动态规划

首先，对于字符串中每一个单独的字符来说，其本身就是一个最小的回文子串，即 s[i] (0 <= i < n);
其次，对于长度为1的回文子串 s[i]，若其前后字符相等，即 s[i-1] = s[i+1],则s[i-1 : i+1]为一个长度为3的回文子串；
若s[i] = s[i+1], 则s[i : i+1]是一个长度为2的回文子串，如果其前后字符相等，即s[i - 1] = s[i + 2], 则s[i-1 : i+2]为一个长度为4的子串；
可以从子串长度出发，遍历字符串中所有长度为1、2的回文子串，将其赋值为true，再对其前后两个字符是否相等进行判断。

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         int len = s.length();
  4.         if (len < 2){
  5.             return s;
  6.         }
  8.         int max_len = 1;
  9.         int begin = 0;
  10.         boolean[][] dp = new boolean[len][len];
  12.         for(int i = 0; i < len; i++){
  13.             dp[i][i] = true;
  14.         }
  16.         char[] charArray = s.toCharArray();
  17.         for(int L = 2; L <= len; L++){
  18.             for(int i = 0; i < len; i++){
  19.                 int j = L + i - 1;
  20.                 if(j >= len){
  21.                     break;
  22.                 }
  24.                 if(charArray[i] != charArray[j]){
  25.                     dp[i][j] = false;
  26.                 }else{
  27.                     if (j - i < 3){
  28.                         dp[i][j] = true;
  29.                     }else{
  30.                         dp[i][j] = dp[i + 1][j - 1];
  31.                     }
  32.                 }
  34.                 if (dp[i][j] == true && j - i + 1 > max_len){
  35.                     max_len = j - i + 1;
  36.                     begin = i;
  37.                 }
  38.             } 
  39.         }
  40.         return s.substring(begin, begin + max_len); 
  41.     }
  42. }

方法2：中心扩展