力扣---5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

提示：
    1 <= s.length <= 1000
    s 仅由数字和英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 由于回文串的特点，可以从中央一点出发，两边到中央点的字符相同。需要注意的是，有两种回文，一种是中心点是某个字符，另一种是中心点在两个相邻字符的中间。

可以理解为回文串的长度是单数还是双数。

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i ++) {
            int tem = 1;
            while (i - tem >= 0 && i + tem < arr.length && arr[i - tem] == arr[i + tem]) {
                tem ++;
            }
            tem -= 1;
            if (res.length() < 2 * tem + 1) {
                res = s.substring(i - tem, i + tem + 1);
            }
            tem = 0;
            while (i - 1 - tem >= 0 && i + tem < arr.length && arr[i - 1 - tem] == arr[i + tem]) {
                tem ++;
            }
            if (res.length() < 2 * tem) {
                res = s.substring(i - tem, i + tem);
            }
        }
        return res;
    }
}

注意到在循环中会使用大量的substring方法，由于javaString不可改变的特点，会占用一定的空间和时间，可以只保存位置和向两端移动的范围，进行优化，

class Solution {
    public String longestPalindrome(String s) {
//        0存储下标，1存储移动距离，2存储长度，3存储方式（单或双）
        int[] res = new int[4];
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i ++) {
            int tem = 1;
            while (i - tem >= 0 && i + tem < arr.length && arr[i - tem] == arr[i + tem]) {
                tem ++;
            }
            tem -= 1;
            if (res[2] < 2 * tem + 1) {
//                res = s.substring(i - tem, i + tem + 1);
                res[0] = i;
                res[1] = tem;
                res[2] = tem * 2 + 1;
                res[3] = 1;
            }
            tem = 0;
            while (i - 1 - tem >= 0 && i + tem < arr.length && arr[i - 1 - tem] == arr[i + tem]) {
                tem ++;
            }
            if (res[2] < 2 * tem) {
//                res = s.substring(i - tem, i + tem);
                res[0] = i;
                res[1] = tem;
                res[2] = tem * 2;
                res[3] = 0;
            }
        }
        return res[3] == 0 ? s.substring(res[0] - res[1], res[0] + res[1]) : s.substring(res[0] - res[1], res[0] + res[1] + 1);
    }
}

多试几次， 可以看到，速度快了那么一丁点(oﾟ▽ﾟ)o