Approach 1

本题我是先用动态规划解出的，其实我觉得动态规划也足矣了，不过还有更好的方法.
复杂度分析：

  • 时间复杂度: 5. Longest Palindromic Substring - 图1
  • 空间复杂度: 5. Longest Palindromic Substring - 图2不过我做了一定的优化，变成了5. Longest Palindromic Substring - 图3

代码如下：

  1. class Solution {
  2.   public String longestPalindrome(String s) {
  3.     if (s == null || s.isEmpty()) {
  4.       return s;
  5.     }
  7.     int len = s.length();
  8.     boolean[][] isPalin = new boolean[2][len];  // i: currentLen % 2, j: startIdx
  10.     for (int i = 0; i < len; ++i) {
  11.       isPalin[0][i] = true;
  12.       isPalin[1][i] = true;
  13.     }
  15.     int maxLen = 1;
  16.     int targetIdx = 0;
  18.     for (int l = 2; l <= len; ++l) {
  19.       for (int idx = 0; idx <= len - l; ++idx) {
  20.         if (isPalin[l%2][idx+1] && s.charAt(idx) == s.charAt(idx+l-1)) {
  21.           isPalin[l%2][idx] = true;
  22.           if (l > maxLen) {
  23.             maxLen = l;
  24.             targetIdx = idx;
  25.           }
  26.         }
  27.         else {
  28.           isPalin[l%2][idx] = false;
  29.         }
  30.       }
  31.     }
  33.     return s.substring(targetIdx, targetIdx + maxLen);
  34.   }
  35. }

不过在此基础上，可以将空间复杂度降为5. Longest Palindromic Substring - 图4，我们使用动态规划的原因是因为动态规划可以记忆一些东西，避免重复计算，但是在本道题中，仔细看看就会发现，其实相对于自底向上的方法，自顶向下的方法并没有做大量重复计算，所以动态规划是不必要的。

Approach 2

利用镜像，设定一个pivot，然后不断扫描左右两边的值
复杂度分析：

  • 时间复杂度: N个pivot，扫描每个需要5. Longest Palindromic Substring - 图5，整体复杂度是5. Longest Palindromic Substring - 图6
  • 空间复杂度：不需要记忆任何东西，所以是5. Longest Palindromic Substring - 图7

代码如下:

  1. class Solution {
  2.   public String longestPalindrome(String s) {
  3.     if (s == null || s.isEmpty()) {
  4.       return s;
  5.     }
  6.     int maxLen = 1;
  7.     int startIdx = 0;
  8.     for (int i = 0; i < s.length(); ++i) {
  9.       int len1 = expand(s, i, i);
  10.       int idx1 = i - len1 / 2;
  11.       int len2 = expand(s, i, i + 1);
  12.       int idx2 = i - len2 / 2 + 1;
  14.       if (len1 > maxLen) {
  15.         maxLen = len1;
  16.         startIdx = idx1;
  17.       }
  18.       if (len2 > maxLen) {
  19.         maxLen = len2;
  20.         startIdx = idx2;
  21.       }
  22.     }
  24.     return s.substring(startIdx, startIdx + maxLen);
  25.   }
  27.   private int expand(String s, int left, int right) {
  28.     while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
  29.       --left;
  30.       ++right;
  31.     }
  32.     return (right - 1) - (left + 1) + 1;
  33.   }
  34. }