题目

给定一个字符串 s ，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000 。

思路

之前想过了,但是一直没想出来，思路过于狭隘，只好参考题解。

解法一

中心扩展方式。思路就是先找到中心点，然后向左向右同时遍历，如果左右相等，则继续遍历，如果左右不相等，则遍历结束，得到的就是最长回文子串

public String longestPalindrome3(String s) {
    if (s == null || s.isEmpty()) {
        return s;
    }
    int start = 0;
    int end = 0;
    for (int i = 0; i < s.length(); i++) {
        //因为中心点可能是某个字符，也可能在两个字符中间，例如 cddf ,中心点就在 dd 之间
        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 l , int r) {
    while (l >= 0 && r < s.length() && s.charAt(r) == s.charAt(l)) {
        l--;
        r++;
    }
    return r - l - 1;
}

循环条件就是，左右位置在字符串长度内，并且左右位置相等， 因为回文字符串可能是 cddc 这种形式，也可能是 cdc 这种形式，所以两种情况都需要考虑。
时间复杂度是O(n²）
空间复杂度是O(1）

解法二

最长回文子串，左右结果相等的，所以可以把字符串倒置，然后找到这两个字符串公共子串。使用动态规划处理。 思路就是申请一个二维数组，然后判断对应的字符串是否相等，相等的话，arr[i][j]=a[i-1][j-1]+1; 当 i = 0 或者 j = 0 的时候单独分析，字符相等的话 arr [ i ][ j ] 就赋为 1 。 arr [ i ][ j ] 保存的就是公共子串的长度。但求出最长公共子串后，并不一定是回文串，我们还需要判断该字符串倒置前的下标和当前的字符串下标是不是匹配。

public String longestPalindrome(String s) {
    //字符串倒置
    String reverseStr = new StringBuffer(s).reverse().toString();

    int maxLen = 0;//最大长度是0；
    int maxEnd = 0;//最长的回文字符串的结束为止

    int length = s.length();
    int[][] cell = new int[length][length];
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length; j++) {
            if (s.charAt(i) == reverseStr.charAt(j)) {
                if (i == 0 || j == 0) {//说明是第一个匹配成功的，那么在二维数组相应的位置存入1
                    cell[i][j] = 1;
                } else {
                    cell[i][j] = cell[i - 1][j - 1] + 1;
                }
            } else {
                //说明这两个字符串不相等，那么就往二维数组中相应的位置存入0
                cell[i][j] = 0;
            }

            if (cell[i][j] > maxLen) {
                //倒置前该字符对应的坐标，
                int beforRevInde = length - 1 - j;
                //字符串倒置前的下标和当前的字符串下标是不是匹配。
                if (beforRevInde + cell[i][j] - 1 == i) {
                    //如果这个是最长回文子串的话，那么加上回文子串的长度，应该是和倒置前的 i 相等的
                    maxLen = cell[i][j];
                    maxEnd = i;
                }

            }
        }
    }
    return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
}

时间复杂度：两层循环 O(n²)。
空间复杂度：一个二维数组 O(n²)。

优化空间复杂度

更新一列，其实只用到了上一列的数据，上上一列的数据是用不到的，使用一个二维数组即可了。即空间复杂度是O(n)，但是更新 arr [i] 的时候我们需要 arr[i-1] 的信息，所以每次只能倒着更新，从尾部往头部更新，于是就有了下面的代码

public String longestPalindromeBetter(String s) {
    if (s == null || s.equals("")) {
        return s;
    }
    //字符串倒置
    String reverseStr = new StringBuffer(s).reverse().toString();

    int maxLen = 0;//最大长度是0；
    int maxEnd = 0;//最长的回文字符串的结束为止

    int length = s.length();
    int[] cell = new int[length];
    for (int i = 0; i < length; i++) {
        for (int j = length - 1; j >= 0; j--) {
            if (s.charAt(i) == reverseStr.charAt(j)) {
                if (i == 0 || j == 0) {//说明是第一个匹配成功的，那么在二维数组相应的位置存入1
                    cell[j] = 1;
                } else {
                    cell[j] = cell[j - 1] + 1;
                }
            } else {
                //说明这两个字符串不相等，那么就往二维数组中相应的位置存入0
                cell[j] = 0;
            }

            if (cell[j] > maxLen) {
                //倒置前该字符对应的坐标，
                int beforRevInde = length - 1 - j;
                //字符串倒置前的下标和当前的字符串下标是不是匹配。
                if (beforRevInde + cell[j] - 1 == i) {
                    //如果这个是最长回文子串的话，那么加上回文子串的长度，应该是和倒置前的 i 相等的
                    maxLen = cell[j];
                    maxEnd = i;
                }

            }
        }
    }
    return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
}

学习到的知识：
这样也是可以求得两个字符串的最长公共子序列的，
还有就是动态规划。

路漫漫其修远兮，吾将上下而刷题。
— 搬运地址：

详细通俗的思路分析，多解法