Description

5. 最长回文子串
难度中等3028
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

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

Solution

暴力解

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         if (s.length() < 2){
  4.             return s;
  5.         }
  6.         char[] cs = s.toCharArray();
  7.         int start = 0, maxLen = 1;
  8.         for (int i = 0; i < cs.length - 1; i ++){   // 分别已 cs[i] 为字符串起点
  9.             for (int j = i + 1; j < cs.length; j ++){  // cs[j] 为字符串结尾
  10.                 if (!validate(cs, i, j)){  //判断是否是 cs[i] ~ cs[j] 的字符串是否是回文串
  11.                     continue;
  12.                 }
  13.                 if (maxLen < (j - i + 1)){
  14.                     start = i;
  15.                     maxLen = j - i + 1;
  16.                 }
  17.             }
  18.         }
  19.         return s.substring(start, start+maxLen);
  20.     }
  21.     // 判断字符串是否是回文串
  22.     private boolean validate(char[] cs, int left ,int right){
  23.         while (left < right){
  24.             if (cs[left] != cs[right]){
  25.                 return false;
  26.             }
  27.             left ++;
  28.             right --;
  29.         }
  30.         return true;
  31.     }
  33. }

动态规划

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         if (s.length() < 2) return s;
  4.         int len = s.length();
  5.         char[] cs = s.toCharArray();
  6.         boolean[][] dp = new boolean[len][len];
  7.         // 状态初始化，单个字符为回文串
  8.         for (int i = 0; i < len; i ++){
  9.             dp[i][i] = true;
  10.         }
  11.         // i:字符串起点，j:字符串结尾
  12.         int start = 0, maxLen = 1;
  13.         for (int j = 0; j < len; j ++){
  14.             for(int i = 0; i < len; i ++){
  15.                 if ( i >= j )
  16.                    break; 
  17.                 if (cs[i] != cs[j]){  // 首尾字符不相同
  18.                     dp[i][j] = false;
  19.                     continue;
  20.                 }
  21.                 // 首尾字符相同的情况
  22.                 int substrlen = j - i + 1;
  23.                 if (substrlen == 2){ // 长度等于2的情况，此时是回文串，如 aa 
  24.                     dp[i][j] = true;
  25.                 }else{  // 长度大于2的情况，此时判断子串 cs[i+1] ~ cs[j-1] 是不是回文串  
  26.                     dp[i][j] = dp[i+1][j-1];  
  27.                 }
  28.                 // 记录最大的回文子串
  29.                 if (dp[i][j] && substrlen > maxLen){
  30.                         maxLen = substrlen;
  31.                         start = i;
  32.                 }
  33.             }
  34.         }
  35.         return s.substring(start, start + maxLen);
  36.     }
  37. }