第五题：最长回文子串

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

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

V1版本

开始觉得这题和题3.无重复字符的最长子串一样，甚至更简单，以为只需要找到两个最长的重复的字符，然后截取出中间的字符返回就行了
结果是一开始就误解了其回文串的意思，导致修改提交了几次都错了
回文的意思是正着念和倒着念一样，如：上海自来水来自海上
对应的最长回文串示例:

  "babad" ==> bab
  "" ==> ""
  "ac" ==> a
  "ccc" ==> ccc
  "abcda" ==> a

后续知道回文串的用意后，想到的是最长回文串其实最主要的还是要看是否有重复的字符，
然后校验最是否满足回文串的要求，如果满足就直接截取字符串返回
没有满足的则按没有满足的退出
1.首先维护的是一个大顶堆，里面保存的是带有重复的字符的起始位置数组
2.依次取出大顶堆中维护的数组，去校验是否满足回文串要求，对于相同长度的回文串，随便返回哪个都行
代码如下:

public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        // map用于维护 char字符与它出现过的下标位置
        Map<Character, List<Integer>> map = new HashMap<>();
        // 大顶堆
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(10, Comparator.comparingInt(o -> (o[0] - o[1])));

        // 临时list
        List<Integer> list;
        for (int i = 0; i < s.length(); i++) {
            // 第一次出现，添加进map就退出
            if (!map.containsKey(s.charAt(i))) {
                list = new ArrayList<>(2);
                list.add(i);
                map.put(s.charAt(i), list);
                continue;
            }

            // 获取历史list
            list = map.get(s.charAt(i));
            for (Integer index : list) {
                // 有重复的情况，将出现的位置分别写入到大顶推中
                maxHeap.add(new int[] {index, i});
            }
            list.add(i);
        }
        int[] poll;
        while (maxHeap.size() > 0) {
            poll = maxHeap.poll();
            if (checkLongestPalindrome(s, poll[0], poll[1])) {
                // 由于是前闭后开，end + 1
                return s.substring(poll[0], poll[1] + 1);
            }
        }
        return s.substring(0,1);
    }

    /**
     * 校验是否满足回文串要求
     */
    public boolean checkLongestPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

知道这种方式运行效率会不高，空间用的也比较多，但没想到会这么惨

image.png

V2版本

一直对这个回文串迷迷糊糊的，看了官方的解析顿时感觉豁然开朗
引用leecode原话：
对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。
例如：
对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。
看到官方有三种方式

1.动态规划
2.中心扩展算法
3.Manacher算法
文字太多，先按自己想到的来实现一下自己的V2版本，可能会和中心扩展的思路会比较像
每次循环都将 p(i - 1,i + 1) 与 p（i,i + 1)进行扩散，直至护展到不匹配为止，代码如下

public String longestPalindrome(String s) {
        // 提前退出
        if (s.length() < 2) {
            return s;
        }
        int len = s.length();
        int start = 0;
        int maxLength = 0;
        // 临时长度
        int length;
        // 临时扩展次数
        int diffusionNum;
        for (int i = 0; i < len - 1; i++) {
            diffusionNum = getDiffusionNum(s, i - 1, i + 1);
            if (diffusionNum > 0) {
                length = diffusionNum * 2 + 1;
                if (length > maxLength) {
                    start = i - diffusionNum;
                    maxLength = length;
                }
            }

            diffusionNum = getDiffusionNum(s, i, i + 1);
            if (diffusionNum > 0) {
                length = diffusionNum * 2;
                if (length > maxLength) {
                    start = i - diffusionNum + 1;
                    maxLength = length;
                }
            }
        }
        maxLength = maxLength == 0? 1: maxLength;
        return s.substring(start, start + maxLength);
    }
    /**
     * 获取扩展次数
     */
    private int getDiffusionNum(String s, int i, int j) {
        // 扩展次数
        int num = 0;
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            num++;
            i--;
            j++;
        }
        return num;
    }

image.png

虽然都有提升，但执行时间还是挺久的，代码的重复率也挺高的

V3版本

V3版本参考一官方的中心扩展法代码
将两种扩散的后的处理逻辑做了合并，获了长度时还考虑了为负数的情况，很强大，后面遇到这种类型的问题不知道能不能灵活运用上，代码如下

public String longestPalindrome(String s) {
        // 提前退出
        if (s.length() < 2) {
            return s;
        }
        int start = 0, end = 0, len;
        for (int i = 0; i < s.length(); i++) {
            len = Math.max(getLen(s, i, i), getLen(s, i, i+1));
            // 屏蔽了两种实现的复杂度
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    /**
     * 获取长度
     */
    private int getLen(String s, int start, int end) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
        }
        // 还考虑了负数的情况
        return end - start - 1;
    }

image.png

依旧需要30几ms,官文的几个代码都直接提交了一份，都需要几十ms，在评论区一位大佬的代码只需要4ms

image.png

执行确认了一下，是个狠人

image.png
大佬的代码先贴出来供大家参考

public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        // 保存起始位置，测试了用数组似乎能比全局变量稍快一点
        int[] range = new int[2];
        char[] str = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            // 把回文看成中间的部分全是同一字符，左右部分相对称
            // 找到下一个与当前字符不同的字符
            i = findLongest(str, i, range);
        }
        return s.substring(range[0], range[1] + 1);
    }

    public static int findLongest(char[] str, int low, int[] range) {
        // 查找中间部分
        int high = low;
        while (high < str.length - 1 && str[high + 1] == str[low]) {
            high++;
        }
        // 定位中间部分的最后一个字符
        int ans = high;
        // 从中间向左右扩散
        while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) {
            low--;
            high++;
        }
        // 记录最大长度
        if (high - low > range[1] - range[0]) {
            range[0] = low;
            range[1] = high;
        }
        return ans;
    }

大佬对这题的思路就更犀利了，因为上述的方式和官方的方式，步长都是p(i,i)及p(i,i+1)然后进行扩散，
这位大佬其实也是这种，不过他遇到连续重复的情况会将步长拉大
例如 abbbbbbbbbbbbbc这种字符串时
当解析到第一个b所在的位置时，传统做法是就地扩散，这位大佬是直接将结束位置移动到最后一个b的位置，
因为相同的字符，无论奇数还是偶数个，都会是回文字串，且下次解析时，直接从最后一个b的位置开始解析，
如果遇到全一样的字符的时候，只需要解析一次，时间复杂度为O(n)，就尼玛离谱