题目

image.png

思路

  • 暴力法
    • 找到每个相同字符的下标i，j，然后再比较i，j区间的字符串是否为回文字符串，是则记录此时最大的长度的回文字符串
  • 中心扩散方法
    • 以每个下标开始扩散，判断其左右两边最大长度能够满足回文，并记录此时的长度

代码

  1.     1.暴力超时
  2.     public String longestPalindrome(String s) {
  3.         int len = s.length();
  4.         if (len <= 1) return s;
  5.         String res = "";
  6.         for (int i = 0; i < len; i++) {
  7.           for (int j = i + 1; j < len; j++) {
  8.               if (s.charAt(i) == s.charAt(j)) {
  9.                   int m = i, n = j;
  10.                   while (m < n && s.charAt(m) == s.charAt(n)) {
  11.                       m++;
  12.                       n--;
  13.                   }
  14.                   String str = s.substring(i, j + 1);
  15.                   res = m >= n && str.length() > res.length() ? str : res;
  16.               }
  17.           }
  18.         }
  19.         return res.length() < 1 ? String.valueOf(s.charAt(0)) : res;
  20.     }
  22.       //2. 中心扩散方法
  23.     public String longestPalindrome(String s) {
  24.         if (s == null) return "";
  25.         int start = 0, end = 0;
  26.         for (int i = 0; i < s.length(); i++) {
  27.             //奇数对称
  28.             int len1 = expandAroundCenter(s, i, i);
  29.             //偶数对称
  30.             int len2 = expandAroundCenter(s, i, i + 1);
  31.             int len = Math.max(len1, len2);
  32.             if (len > end - start) {
  33.                 //偶数会多一位
  34.                 start = i - (len - 1) / 2;
  35.                 end = i + len / 2 ;
  36.             }
  37.         }
  38.         return end - start == 0 ? s.substring(0, 1) : s.substring(start, end + 1);
  39.     }
  41.     public int expandAroundCenter(String s, int left, int right) {
  42.         while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
  43.             left--;
  44.             right++;
  45.         }
  46.         return right - left - 1;
  47.     }
  49.      //1.暴力递归
  50.     public String longestPalindrome(String s) {
  51.         int start = 0, end = 0;
  52.         for (int i = 0; i < s.length(); i++) {
  53.             int len1 = recur(s, i, i + 1) + 2;
  54.             int len2 = recur(s, i, i) + 1;
  55.             int len = Math.max(len1, len2);
  56.             if (len > end - start) {
  57.                 //偶数会多一位
  58.                 start = i - (len - 1) / 2;
  59.                 end = i + len / 2 ;
  60.             }
  61.         }
  62.         return end - start == 0 ? s.substring(0, 1) : s.substring(start, end + 1);
  63.     }
  65.     public int recur(String s, int i, int j) {
  66.         if (i < 0 || j >= s.length()) return -2;
  67.         if (s.charAt(i) == s.charAt(j)) 
  68.             return recur(s, i - 1, j + 1) + 2;
  69.         return -2;
  70.     }
  72.     //2. 动态规划
  73.     public String longestPalindrome(String s) {
  74.         //dp[i][j]表示字符串下标i到j之间是否为回文
  75.         int len = s.length(), start = 0, end = 0;
  76.         boolean[][] dp = new boolean[len][len];
  77.         for (int i = 0; i < len; i++) {
  78.             dp[i][i] = true;
  79.         }
  80.         for (int j = 1; j < len; j++) {
  81.             for (int i = 0; i < j; i++) {
  82.                 if (s.charAt(i) != s.charAt(j)) {
  83.                     dp[i][j] = false;
  84.                 } else {
  85.                     if (j - i < 3) {
  86.                         dp[i][j] = true;
  87.                     } else {
  88.                         dp[i][j] = dp[i + 1][j - 1];
  89.                     }
  90.                     if (dp[i][j] && j - i > end - start) {
  91.                         start = i;
  92.                         end = j; 
  93.                     }
  94.                 }
  95.             }
  96.         }
  97.         return end - start == 0 ? s.substring(0, 1) : s.substring(start, end + 1);
  98.     }

最长回文子串