题目地址

思路一（时间复杂度过高，朴素思路）：

1. 使用分格子的思想，求出当格子为1、2、3、4...max(max = 字符串长度)时是否存在回文子串
2. 如果当格子中的字符串是回文的时候，看看是否需要更新回文子串最大值

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1)
            return s;
        String maxStr = "";
        int max = s.length();
        int l = 1;
	// 格子的长度 
        while (l <= max) {
	    // 遍历原字符串数组
            for(int start = 0;start <= max - l; start ++) {
                char[] copy = copy(s, start, l);
                if (isTarget(copy)) {
                    // 判断是否需要更新最大值
                    if (l >= maxStr.length()) {
                        maxStr = new String(copy);
                    }
                }   
            }
            l++;
        }
        return maxStr;

    }

    boolean isTarget(char[] ch) {
        int left = 0;
        int right = ch.length -1;
        while (left <= right) {
            if (ch[left] !=  ch[right])
                return false;
            left++;
            right--;
        }
        return true;
    }

    char[] copy(String s , int start , int len) {
        char[] ch = new char[len];
        char[] c = s.toCharArray();
        for (int i = 0; i < len ;i++ ) {
            ch[i] = c[start + i];
        }
        return ch;
    }
}

思路二（动态规划）

1. 根据格子进行分割，分出子字符串的长度可能性
2. 当判断s[i,j]是否为回文的时候，如果s[i+1,j-1]为回文，那么当s[i] == s[j],则说明s[i,j]就是回文
3. 原题则变成判断s[0...i,0...j]即len*len中情况中属于回文，且长度最长的
4. 只需要记录起始和字符串长度就可以找到完整的回文

  // 构造判断矩阵判断i-j的字符串是否为回文
  boolean[][] matrix;

  public String longestPalindrome(String s) {
    if (s.length() <= 1) return s;
    char[] chs = s.toCharArray();
    int len = chs.length;
    matrix = new boolean[len][len];
    for (int i = 0; i < len; i++) {
      // 初始化，i到i一定是回文
      matrix[i][i] = true;
    }

    int max = 1;
    int left = 0;
    // 格子大小
    for (int i = 2; i <= len; i++) {
      // 判断下标 j 到j + i - 1是否为回文
      for (int j = 0; j <= len - i; j++) {
        if (chs[j] == chs[j + i - 1]) {
          // 相邻两个格子的相等即为回文
          if(i == 2) {
            matrix[j][j + i - 1] = true;
            matrix[j + i - 1][j] = true;
          }
          if (matrix[j + 1][j + i - 2]) {
            matrix[j][j + i - 1] = true;
            // 如果比最长字符串长，则更新最长字符串起始下标以及长度
            if (i > max) {
              max = i;
              left = j;
            }
          }
        }
      }
    }
    return s.substring(left, left + max);
  }

思路三（中心扩散）

1. 回文的特点，两边的字符串相等，因此可以通过先寻找回文中心，然后再不断扩散判断s[i] ?= s[j],如果不相等，则循环判断结束，算出以该点为中心的回文最长长度
2. 需要注意字符串的奇偶性，所以判断的时候存在两种情况
   （1）回文中心为1个字符
   （2）回文中心为2个字符构成

添加AI版本的中心扩散解法

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 回文子串可能为单中心，数目为奇数；可能为双中心，数目为偶数
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            // 当回文子串最大值更新的时候更新起始点和结束点
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
           }
        }
        return s.substring(start, end + 1);
    }
    // 中心扩散
    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}

Q.E.D.