??首先讓我們來(lái)看Leetcode上的一道題绎巨。
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
??題意解析：給定一個(gè)字符串S做祝，求這個(gè)字符串的最長(zhǎng)回文子串。所謂回文字符串就是正著讀和反著讀結(jié)果都一樣的字符串株搔，如aba剖淀，bab。
??解法：
（1）暴力求解法：即循環(huán)去枚舉字符串中的每個(gè)字符纤房，這種解法的時(shí)間復(fù)雜度為O(n^3)纵隔，再leetcode上應(yīng)該過(guò)不了，所以沒(méi)有去實(shí)現(xiàn)炮姨。
（2）中心擴(kuò)展法：即以某個(gè)元素為中心捌刮，分別去計(jì)算假設(shè)回文子串長(zhǎng)度為偶數(shù)的情況和回文子串長(zhǎng)度為奇數(shù)的情況下的最長(zhǎng)的回文串，這種解法時(shí)間復(fù)雜度為O(n^2)舒岸，時(shí)間復(fù)雜度比第一種算法時(shí)間減少了一個(gè)指數(shù)級(jí)绅作，嘗試著去實(shí)現(xiàn)它，代碼如下：
package cn.test.leetcode;
/**
* Created by GavinCee on 2019/5/1.
*/
public class PalindromicStr {
public static void main(String[] args) {
PalindromicStr palindromicStr = new PalindromicStr();
String testStr1 = "babad";
String testStr2 = "cbbd";
String testStr3 = "gabbacg";
String testStr4 = "gabbac";
String testStr5 = "cabbac";
System.out.println(palindromicStr.longestPalindrome(testStr1));
System.out.println(palindromicStr.longestPalindrome(testStr2));
System.out.println(palindromicStr.longestPalindrome(testStr3));
System.out.println(palindromicStr.longestPalindrome(testStr4));
System.out.println(palindromicStr.longestPalindrome(testStr5));
}
public String longestPalindrome(String s) {
if(s == null) {
return null;
}
if(s.equals("")) {
return "";
}
int maxLength = 0;
String result = "";
int len = 1;
if(s.length() > 1) {
len = s.length() - 1;
}
for (int i = 0; i < len; i++) {
String tmp = s.charAt(i) + "";
//1. if the substring length is odd ,so the index is mid.
for(int j = i - 1, k = i + 1;j >=0 && k < s.length(); j--,k++) {
if(s.charAt(j) == s.charAt(k)) {
tmp = s.charAt(j) + tmp + s.charAt(k);
} else {
break;
}
}
if(tmp.length() > maxLength) {
maxLength = tmp.length();
result = new String(tmp);
}
//2' if the substring length is even, the right need plus 2
if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
tmp = s.charAt(i) + "" + s.charAt(i + 1);
for(int j = i - 1, k = i + 2;j >=0 && k < s.length(); j--,k++) {
if(s.charAt(j) == s.charAt(k)) {
tmp = s.charAt(j) + tmp + s.charAt(k);
} else {
break;
}
}
if(tmp.length() > maxLength) {
maxLength = tmp.length();
result = new String(tmp);
}
}
}
return result;
}
}
??提交到leetcode后蛾派，仍然還是會(huì)報(bào)時(shí)間超時(shí)俄认。所以這種解法還被pass掉了。暫時(shí)無(wú)優(yōu)化思路洪乍，借助百度眯杏，了解到還有一種時(shí)間復(fù)雜度為O(n)的算法，下面強(qiáng)調(diào)介紹一下該算法壳澳，并順便整理一下思路岂贩。
（3）Manacher算法
Manacher算法提供了一種巧妙的方法，講長(zhǎng)度為奇數(shù)的回文串和長(zhǎng)度為偶數(shù)的回文串一起考慮進(jìn)來(lái)巷波，具體做法是在原字符串的每?jī)蓚€(gè)相鄰的字符中間插入一個(gè)分隔符萎津，同時(shí)在原字符串的首尾也都添加上分隔符，該分隔符的要求是不要在原字符串內(nèi)出現(xiàn)抹镊，避免出現(xiàn)混淆锉屈。如下所示：
| 原字符串 | 轉(zhuǎn)換后的字符串 |
|---|---|
| babad | #b#a#b#a#d# |
在Manacher算法中用到一個(gè)非常重要的輔助數(shù)組，我們將轉(zhuǎn)換后的字符串定義為字符數(shù)組str[i]垮耳，其輔助數(shù)組定義為len[i]颈渊。其中l(wèi)en[i]中的元素為以str[i]為中心時(shí)的回文串的最右端字符到str[i]的位置的長(zhǎng)度，如下圖所示氨菇，當(dāng)i等于3時(shí)儡炼，str[i]為a妓湘，以str[i]為中心的回文串是#b#a#b#查蓉，則len[i]為最右字符#到a的長(zhǎng)度，即len[i]=4榜贴。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| str[i] | # | b | # | a | # | b | # | a | # | d | # |
| len[i] | 1 | 2 | 1 | 4 | 1 | 4 | 1 | 2 | 1 | 2 | 1 |
該輔助數(shù)組len[i]有一個(gè)性質(zhì)豌研，就是len[i] -1就等于該位置所在的字符為中心的原字符串的回文子串的長(zhǎng)度妹田。
證明：在轉(zhuǎn)換后的字符串str，因?yàn)榍昂蠖疾迦肓朔指舴楣玻械幕匚淖哟拈L(zhǎng)度都是奇數(shù)鬼佣，len[i]為回文最右字符到回文中心的長(zhǎng)度，那么對(duì)于以str[i]為中心的回文子串的長(zhǎng)度就是2*len[i] - 1霜浴，算上首尾的分隔符晶衷，那么該回文子串會(huì)有l(wèi)en[i]個(gè)分隔符，所以說(shuō)原回文子串的長(zhǎng)度就是（2len[i] - 1）- len[i] = len[i] - 1阴孟。
那么計(jì)算最長(zhǎng)的回文子串長(zhǎng)度晌纫，即為計(jì)算len[i]數(shù)組中的最大值。
假設(shè)0<= j <= i永丝，從左往右開始計(jì)算len[i]锹漱，在計(jì)算len[i]的時(shí)候，由于j<=i慕嚷，那么在計(jì)算len[i]之前l(fā)en[j]已經(jīng)計(jì)算過(guò)了哥牍，假設(shè)mx為之前計(jì)算過(guò)的回文子串的最右端點(diǎn)位置，id為這個(gè)回文子串的中心點(diǎn)位置喝检，那么len[id] = mx- id + 1嗅辣。
（1）當(dāng)i <= mx
此時(shí)i在以id為中心的回文串，假設(shè)i相對(duì)于中心點(diǎn)id的對(duì)稱點(diǎn)為j蛇耀，len[j]已經(jīng)計(jì)算過(guò)了辩诞。
假設(shè)len[j] < mx - i，即如下圖所示
此時(shí)說(shuō)明以j為中心的回文串一定在以id為中心的回文串內(nèi)部纺涤，且i和j關(guān)于id對(duì)稱译暂，由回文串的定義可知，一個(gè)回文串反過(guò)來(lái)仍然是回文串撩炊，所以以i為中心的回文串長(zhǎng)度至少和以j為中心的回文串長(zhǎng)度相等外永，即len[i] >= len[j]，因?yàn)閘en[j] < mx - i拧咳，所以i + len[j] < mx伯顶，
假設(shè)len[j] >= mx - i，如下圖所示
由于回文的對(duì)稱性骆膝，說(shuō)明以i為中心的回文串可能延伸到mx之外祭衩，而大于mx的部分的字符還沒(méi)有進(jìn)行匹配比較，所以要從mx+1位置開始一個(gè)一個(gè)字符匹配知道失配阅签，匹配完成后及時(shí)更新mx和對(duì)應(yīng)的id以及l(fā)en[i]掐暮。
（2）當(dāng)i >= mx
由于i比mx還大，說(shuō)明對(duì)于中心點(diǎn)為i的回文串還沒(méi)有計(jì)算過(guò)政钟，這個(gè)時(shí)候只能左右展開一個(gè)個(gè)字符的匹配路克，匹配完成之后更新mx位置和對(duì)應(yīng)的id以及l(fā)en[i].
按照以上思路實(shí)現(xiàn)代碼邏輯如下：
package cn.test.leetcode;
/**
* Created by GavinCee on 2019/5/1.
*/
public class PalindromicStr2 {
public static void main(String[] args) {
PalindromicStr2 palindromicStr = new PalindromicStr2();
String testStr1 = "babad";
String testStr2 = "cbbd";
String testStr3 = "gabbacg";
String testStr4 = "gabbac";
String testStr5 = "cabbac";
String testStr = "babadada";
System.out.println(palindromicStr.longestPalindrome(testStr));
System.out.println(palindromicStr.longestPalindrome(testStr1));
System.out.println(palindromicStr.longestPalindrome(testStr2));
System.out.println(palindromicStr.longestPalindrome(testStr3));
System.out.println(palindromicStr.longestPalindrome(testStr4));
System.out.println(palindromicStr.longestPalindrome(testStr5));
}
public String longestPalindrome(String s) {
if(s == null || s.length() < 1){
return "";
}
StringBuilder manacherStr = new StringBuilder("#");
for (int i = 0; i < s.length(); i++) {
manacherStr.append(s.charAt(i) + "#");
}
int[] len = new int[manacherStr.length()];
len[0] = 1;
int maxRightIndex = 0;
int index = 0;
int maxLength = len[0];
int maxIndex = 0;
for(int i = 1; i < manacherStr.length(); i++) {
if(maxRightIndex > i) {
int j = 2 * index - i;
if(len[j] < maxRightIndex - i) {
len[i] = len[j];
} else {
len[i] = maxRightIndex - i + 1;
//從maxRightIndex開始匹配樟结，已經(jīng)匹配了len[i]的長(zhǎng)度了，所以左側(cè)是i-len[i]
while (i - len[i] >= 0 && i+len[i] < manacherStr.length() && manacherStr.charAt(i - len[i]) == manacherStr.charAt(i+len[i])) {
len[i]++;
}
}
}else {
//此時(shí)還沒(méi)有匹配
len[i] = 1;
while (i - len[i] >= 0 && i+len[i] < manacherStr.length() && manacherStr.charAt(i - len[i]) == manacherStr.charAt(i+len[i])) {
len[i] = len[i] + 1;
}
}
if(len[i] + i - 1> maxRightIndex) {
maxRightIndex = len[i] + i - 1;
index = i;
}
if(len[i] > maxLength) {
maxLength = len[i];
maxIndex = i;
}
}
//所以最大回文長(zhǎng)度就是len[] - 1;
String resTmp = manacherStr.substring(maxIndex - maxLength + 1, maxIndex + maxLength -1);
return resTmp.replaceAll("#", "");
}
}
??提交運(yùn)行通過(guò)精算。
