第五題：最長回文子串
給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/check-permutation-lcci
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權，非商業(yè)轉載請注明出處。
V1版本
開始覺得這題和題3.無重復字符的最長子串一樣，甚至更簡單，以為只需要找到兩個最長的重復的字符，然后截取出中間的字符返回就行了
結果是一開始就誤解了其回文串的意思，導致修改提交了幾次都錯了
回文的意思是正著念和倒著念一樣，如：上海自來水來自海上
對應的最長回文串示例:
"babad" ==> bab
"" ==> ""
"ac" ==> a
"ccc" ==> ccc
"abcda" ==> a
后續(xù)知道回文串的用意后，想到的是最長回文串其實最主要的還是要看是否有重復的字符，
然后校驗最是否滿足回文串的要求，如果滿足就直接截取字符串返回
沒有滿足的則按沒有滿足的退出
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.動態(tài)規(guī)劃
2.中心擴展算法
3.Manacher算法
文字太多，先按自己想到的來實現一下自己的V2版本，可能會和中心擴展的思路會比較像
每次循環(huán)都將 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;
}
雖然都有提升，但執(zhí)行時間還是挺久的，代碼的重復率也挺高的
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，在評論區(qū)一位大佬的代碼只需要4ms
執(zhí)行確認了一下，是個狠人
大佬的代碼先貼出來供大家參考
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)然后進行擴散，
這位大佬其實也是這種，不過他遇到連續(xù)重復的情況會將步長拉大
例如 abbbbbbbbbbbbbc這種字符串時
當解析到第一個b所在的位置時，傳統(tǒng)做法是就地擴散，這位大佬是直接將結束位置移動到最后一個b的位置，
因為相同的字符，無論奇數還是偶數個，都會是回文字串，且下次解析時，直接從最后一個b的位置開始解析，
如果遇到全一樣的字符的時候，只需要解析一次，時間復雜度為O(n)，就尼瑪離譜
