第五题：最长回文子串
给定一个字符串 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;
}
知道这种方式运行效率会不高，空间用的也比较多，但没想到会这么惨
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;
}
虽然都有提升，但执行时间还是挺久的，代码的重复率也挺高的
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;
}
依旧需要30几ms,官文的几个代码都直接提交了一份，都需要几十ms，在评论区一位大佬的代码只需要4ms
执行确认了一下，是个狠人
大佬的代码先贴出来供大家参考
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)，就尼玛离谱
