https://leetcode.windliang.cc/ 第一時間發(fā)布
題目描述（中等難度）
給定一個字符串，輸出最長的回文子串域慷〉种希回文串指的是正的讀和反的讀是一樣的字符串李皇，例如 "aba"，"ccbbcc"慰丛。
解法一 暴力破解
暴力求解捍岳，列舉所有的子串，判斷是否為回文串苏潜，保存最長的回文串恤左。
public boolean isPalindromic(String s) {
int len = s.length();
for (int i = 0; i < len / 2; i++) {
if (s.charAt(i) != s.charAt(len - i - 1)) {
return false;
}
}
return true;
}
// 暴力解法
public String longestPalindrome(String s) {
String ans = "";
int max = 0;
int len = s.length();
for (int i = 0; i < len; i++)
for (int j = i + 1; j <= len; j++) {
String test = s.substring(i, j);
if (isPalindromic(test) && test.length() > max) {
ans = s.substring(i, j);
max = Math.max(max, ans.length());
}
}
return ans;
}
時間復(fù)雜度：兩層 for 循環(huán) O（n2），for 循環(huán)里邊判斷是否為回文巧鸭，O（n）纲仍，所以時間復(fù)雜度為 O（n3）郑叠。
空間復(fù)雜度：O（1），常數(shù)個變量署拟。
解法二 最長公共子串
根據(jù)回文串的定義心包，正著和反著讀一樣蟹腾，那我們是不是把原來的字符串倒置了娃殖，然后找最長的公共子串就可以了炉爆。例如，S = " caba"逼裆，S' = " abac"耀怜，最長公共子串是 "aba"桐愉，所以原字符串的最長回文串就是 "aba"左痢。
關(guān)于求最長公共子串（不是公共子序列）抖锥，有很多方法磅废，這里用動態(tài)規(guī)劃的方法竟趾，可以先閱讀下邊的鏈接岔帽。
https://blog.csdn.net/u010397369/article/details/38979077
https://www.kancloud.cn/digest/pieces-algorithm/163624
整體思想就是犀勒，申請一個二維的數(shù)組初始化為 0，然后判斷對應(yīng)的字符是否相等檐盟，相等的話
arr [ i ][ j ] = arr [ i - 1 ][ j - 1] + 1 导犹。
當(dāng) i = 0 或者 j = 0 的時候單獨分析谎痢，字符相等的話 arr [ i ][ j ] 就賦為 1 掰烟。
arr [ i ][ j ] 保存的就是公共子串的長度纫骑。
public String longestPalindrome(String s) {
if (s.equals(""))
return "";
String origin = s;
String reverse = new StringBuffer(s).reverse().toString(); //字符串倒置
int length = s.length();
int[][] arr = new int[length][length];
int maxLen = 0;
int maxEnd = 0;
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++) {
if (origin.charAt(i) == reverse.charAt(j)) {
if (i == 0 || j == 0) {
arr[i][j] = 1;
} else {
arr[i][j] = arr[i - 1][j - 1] + 1;
}
}
if (arr[i][j] > maxLen) {
maxLen = arr[i][j];
maxEnd = i; //以 i 位置結(jié)尾的字符
}
}
}
return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
}
再看一個例子发框，S = "abc435cba"梅惯，S’ = "abc534cba" 铣减，最長公共子串是 "abc" 和 "cba" 缔刹，但很明顯這兩個字符串都不是回文串校镐。
所以我們求出最長公共子串后鸟廓，并不一定是回文串肝箱，我們還需要判斷該字符串倒置前的下標(biāo)和當(dāng)前的字符串下標(biāo)是不是匹配。
比如 S = " caba "退客，S' = " abac " 档玻，S’ 中 aba 的下標(biāo)是 0 1 2 误趴，倒置前是 3 2 1，和 S 中 aba 的下標(biāo)符合看杭，所以 aba 就是我們需要找的楼雹。當(dāng)然我們不需要每個字符都判斷，我們只需要判斷末尾字符就可以谴供。
首先 i 龟劲，j 始終指向子串的末尾字符昌跌。所以 j 指向的紅色的 a 倒置前的下標(biāo)是 beforeRev = length - 1 - j = 4 - 1 - 2 = 1，對應(yīng)的是字符串首位的下標(biāo)萍诱，我們還需要加上字符串的長度才是末尾字符的下標(biāo)裕坊，也就是 beforeRev + arr[ i ] [ j ] - 1 = 1 + 3 - 1 = 3，因為 arr[ i ] [ j ] 保存的就是當(dāng)前子串的長度苗缩，也就是圖中的數(shù)字 3 退盯。此時再和它與 i 比較，如果相等焚挠，則說明它是我們要找的回文串蝌衔。
之前的 S = "abc435cba"曹锨，S' = "abc534cba" 沛简，可以看一下圖示给郊，為什么不符合淆九。
當(dāng)前 j 指向的 c ，倒置前的下標(biāo)是 beforeRev = length - 1 - j = 9 - 1 - 2 = 6毛俏，對應(yīng)的末尾下標(biāo)是 beforeRev + arr[ i ] [ j ] - 1 = 6 + 3 - 1 = 8 炭庙，而此時 i = 2 ，所以當(dāng)前的子串不是回文串煌寇。
代碼的話焕蹄，在上邊的基礎(chǔ)上，保存 maxLen 前判斷一下下標(biāo)匹不匹配就可以了阀溶。
public String longestPalindrome(String s) {
if (s.equals(""))
return "";
String origin = s;
String reverse = new StringBuffer(s).reverse().toString();
int length = s.length();
int[][] arr = new int[length][length];
int maxLen = 0;
int maxEnd = 0;
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++) {
if (origin.charAt(i) == reverse.charAt(j)) {
if (i == 0 || j == 0) {
arr[i][j] = 1;
} else {
arr[i][j] = arr[i - 1][j - 1] + 1;
}
}
/**********修改的地方*******************/
if (arr[i][j] > maxLen) {
int beforeRev = length - 1 - j;
if (beforeRev + arr[i][j] - 1 == i) { //判斷下標(biāo)是否對應(yīng)
maxLen = arr[i][j];
maxEnd = i;
}
/*************************************/
}
}
return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
}
時間復(fù)雜度：兩層循環(huán)，O（n2）。
空間復(fù)雜度：一個二維數(shù)組，O（n2）。
空間復(fù)雜度其實可以再優(yōu)化一下奈惑。
我們分析一下循環(huán)彤叉，i = 0 ，j = 0，1，2 ... 8 更新一列循衰，然后 i = 1 先鱼，再更新一列，而更新的時候我們其實只需要上一列的信息，更新第 3 列的時候催式，第 1 列的信息是沒有用的捐下。所以我們只需要一個一維數(shù)組就可以了。但是更新 arr [ i ] 的時候我們需要 arr [ i - 1 ] 的信息蒸绩，假設(shè) a [ 3 ] = a [ 2 ] + 1，更新 a [ 4 ] 的時候乞娄， 我們需要 a [ 3 ] 的信息，但是 a [ 3 ] 在之前已經(jīng)被更新了，所以 j 不能從 0 到 8 斧吐，應(yīng)該倒過來木张，a [ 8 ] = a [ 7 ] + 1，a [ 7 ] = a [ 6 ] + 1 , 這樣更新 a [ 8 ] 的時候用 a [ 7 ] ，用完后才去更新 a [ 7 ]闷畸，保證了不會出錯失尖。
public String longestPalindrome(String s) {
if (s.equals(""))
return "";
String origin = s;
String reverse = new StringBuffer(s).reverse().toString();
int length = s.length();
int[] arr = new int[length];
int maxLen = 0;
int maxEnd = 0;
for (int i = 0; i < length; i++)
/**************修改的地方***************************/
for (int j = length - 1; j >= 0; j--) {
/**************************************************/
if (origin.charAt(i) == reverse.charAt(j)) {
if (i == 0 || j == 0) {
arr[j] = 1;
} else {
arr[j] = arr[j - 1] + 1;
}
/**************修改的地方***************************/
//之前二維數(shù)組羞芍，每次用的是不同的列将鸵，所以不用置 0 老充。
} else {
arr[j] = 0;
}
/**************************************************/
if (arr[j] > maxLen) {
int beforeRev = length - 1 - j;
if (beforeRev + arr[j] - 1 == i) {
maxLen = arr[j];
maxEnd = i;
}
}
}
return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
}
時間復(fù)雜度：O（n2）。
空間復(fù)雜度：降為 O（n）。
解法三 暴力破解優(yōu)化
解法一的暴力解法時間復(fù)雜度太高，在 leetCode 上并不能 AC 。我們可以考慮诬留，去掉一些暴力解法中重復(fù)的判斷。我們可以基于下邊的發(fā)現(xiàn)腮恩，進(jìn)行改進(jìn)。
首先定義 P（i荡含，j）咒唆。
接下來
所以如果我們想知道 P（i，j）的情況释液，不需要調(diào)用判斷回文串的函數(shù)了全释，只需要知道 P（i + 1，j - 1）的情況就可以了误债，這樣時間復(fù)雜度就少了 O（n）浸船。因此我們可以用動態(tài)規(guī)劃的方法，空間換時間寝蹈，把已經(jīng)求出的 P（i李命，j）存儲起來。
如果 是回文串箫老，那么只要 S [ i ] == S [ j ] 封字，就可以確定 S [ i , j ] 也是回文串了。
求 長度為 1 和長度為 2 的 P ( i , j ) 時不能用上邊的公式耍鬓，因為我們代入公式后會遇到 中 i > j 的情況阔籽，比如求
的話，我們需要知道
牲蜀，而
代表著
是不是回文串笆制，顯然是不對的，所以我們需要單獨判斷各薇。
所以我們先初始化長度是 1 的回文串的 P [ i , j ]项贺，這樣利用上邊提出的公式 芽突，然后兩邊向外各擴(kuò)充一個字符，長度為 3 的颓屑，為 5 的仗岸，所有奇數(shù)長度的就都求出來了。
同理奕删，初始化長度是 2 的回文串 P [ i , i + 1 ]俺泣，利用公式，長度為 4 的完残，6 的所有偶數(shù)長度的就都求出來了伏钠。
public String longestPalindrome(String s) {
int length = s.length();
boolean[][] P = new boolean[length][length];
int maxLen = 0;
String maxPal = "";
for (int len = 1; len <= length; len++) //遍歷所有的長度
for (int start = 0; start < length; start++) {
int end = start + len - 1;
if (end >= length) //下標(biāo)已經(jīng)越界，結(jié)束本次循環(huán)
break;
P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1]) && s.charAt(start) == s.charAt(end); //長度為 1 和 2 的單獨判斷下
if (P[start][end] && len > maxLen) {
maxPal = s.substring(start, end + 1);
}
}
return maxPal;
}
時間復(fù)雜度：兩層循環(huán)谨设，O（n2）熟掂。
空間復(fù)雜度：用二維數(shù)組 P 保存每個子串的情況，O（n2）扎拣。
我們分析下每次循環(huán)用到的 P（i赴肚，j），看一看能不能向解法二一樣優(yōu)化一下空間復(fù)雜度二蓝。
當(dāng)我們求長度為 6 和 5 的子串的情況時誉券，其實只用到了 4 ， 3 長度的情況刊愚，而長度為 1 和 2 的子串情況其實已經(jīng)不需要了踊跟。但是由于我們并不是用 P 數(shù)組的下標(biāo)進(jìn)行的循環(huán)，暫時沒有想到優(yōu)化的方法鸥诽。
之后看到了另一種動態(tài)規(guī)劃的思路
公式還是這個不變
首先定義 P（i，j）衙传。
接下來
遞推公式中我們可以看到决帖，我們首先知道了 i +1 才會知道 i ，所以我們只需要倒著遍歷就行了蓖捶。
public String longestPalindrome(String s) {
int n = s.length();
String res = "";
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); //j - i 代表長度減去 1
if (dp[i][j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
}
時間復(fù)雜度和空間復(fù)雜和之前都沒有變化地回，我們來看看可不可以優(yōu)化空間復(fù)雜度。
當(dāng)求第 i 行的時候我們只需要第 i + 1 行的信息俊鱼，并且 j 的話需要 j - 1 的信息刻像，所以和之前一樣 j 也需要倒敘。
public String longestPalindrome7(String s) {
int n = s.length();
String res = "";
boolean[] P = new boolean[n];
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= i; j--) {
P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
if (P[j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
}
時間復(fù)雜度：不變并闲，O（n2）细睡。
空間復(fù)雜度：降為 O（n ) 。
解法四 擴(kuò)展中心
我們知道回文串一定是對稱的帝火，所以我們可以每次循環(huán)選擇一個中心溜徙，進(jìn)行左右擴(kuò)展湃缎，判斷左右字符是否相等即可。
由于存在奇數(shù)的字符串和偶數(shù)的字符串蠢壹，所以我們需要從一個字符開始擴(kuò)展嗓违，或者從兩個字符之間開始擴(kuò)展，所以總共有 n + n - 1 個中心图贸。
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
時間復(fù)雜度：O（n2）蹂季。
空間復(fù)雜度：O（1）。
解法五 Manacher's Algorithm 馬拉車算法疏日。
馬拉車算法 Manacher‘s Algorithm 是用來查找一個字符串的最長回文子串的線性方法偿洁，由一個叫Manacher的人在1975年發(fā)明的，這個方法的最大貢獻(xiàn)是在于將時間復(fù)雜度提升到了線性沟优。
主要參考了下邊鏈接進(jìn)行講解涕滋。
https://segmentfault.com/a/1190000008484167
https://blog.crimx.com/2017/07/06/manachers-algorithm/
http://ju.outofmemory.cn/entry/130005
https://articles.leetcode.com/longest-palindromic-substring-part-ii/
首先我們解決下奇數(shù)和偶數(shù)的問題，在每個字符間插入"#"净神，并且為了使得擴(kuò)展的過程中何吝，到邊界后自動結(jié)束，在兩端分別插入 "^" 和 "$"鹃唯，兩個不可能在字符串中出現(xiàn)的字符，這樣向解法四那樣中心擴(kuò)展的時候瓣喊，判斷兩端字符是否相等的時候坡慌，如果到了邊界就一定會不相等，從而出了循環(huán)藻三。經(jīng)過處理洪橘，字符串的長度永遠(yuǎn)都是奇數(shù)了。
首先我們用一個數(shù)組 P 保存從中心擴(kuò)展的個數(shù)棵帽，巧合的它也是去掉 "#" 的字符串的總長度熄求，可以看下邊的圖。
用 P 的下標(biāo) i 減去 P[i]逗概，再除以 2 弟晚，就是原字符串的開頭下標(biāo)了。
例如我們找到 P[i] 的最大值為 5 逾苫，也就是回文串的最大長度是 5 卿城，對應(yīng)的下標(biāo)是 6 ，所以原字符串的開頭下標(biāo)是 （6 - 5 ）/ 2 = 0 铅搓。所以我們只需要返回原字符串的第 0 到 第 （5 - 1）位就可以了瑟押。
接下來是算法的關(guān)鍵了，它充分利用了回文串的對稱性星掰。
我們用 C 表示回文串的中心多望，用 R 表示回文串的右邊半徑嫩舟。所以 R = C + P[i] 。C 和 R 所對應(yīng)的回文串是當(dāng)前循環(huán)中 R 最靠右的回文串怀偷。
用 i_mirror 表示當(dāng)前擴(kuò)展的第 i 個字符關(guān)于 C 對應(yīng)的下標(biāo)至壤。
我們現(xiàn)在要求 P [ i ] 如果是解法四，那就向兩邊擴(kuò)展就行了枢纠。但是我們其實可以利用回文串 C 的對稱性像街。i 關(guān)于 C 的對稱點是 i_mirror ，P [ mirror ] = 3晋渺，所以 P [ i ] 也等于 3 镰绎。
有三種情況將會造成直接賦值為 P [ mirror ] 是不正確的。
超出了 R
當(dāng)我們要求 P[i] 的時候木西，P [ mirror ] = 7畴栖，而此時 P [ i ] 并不等于 7 ，為什么呢八千，因為我們從 i 開始往后數(shù) 7 個吗讶，等于 22 ，已經(jīng)超過了最右的 R 恋捆，此時不能利用對稱性了照皆，但我們一定可以擴(kuò)展到 R 的，所以 P [i] 至少等于 R - i = 20 - 15 = 5沸停，會不會更大呢膜毁，我們只需要比較 T[R+1] 和 T[R+1]關(guān)于 i 的對稱點就行了，像解法四一樣一個個擴(kuò)展愤钾。
P [ mirror ] 遇到了左邊界
此時 P [ i ] 賦值成 1 是不正確的瘟滨，出現(xiàn)這種情況的原因是 P [ i_mirror ] 在擴(kuò)展的時候首先是 "#" == "#" ，之后遇到了 "^"和另一個字符比較能颁，也就是到了邊界杂瘸，才終止循環(huán)的。而 P [ i ] 并沒有遇到邊界伙菊，所以我們可以接著擴(kuò)展败玉，就像之前一樣。
i 等于了 R
此時我們先把 P [ i ] 賦值為 0 占业，然后一步一步擴(kuò)展就行了绒怨。
就這樣一步一步的求出每個 P [ i ]，當(dāng)求出的 P [ i ] 的右邊界大于當(dāng)前的 R 時谦疾，我們就需要更新 C 和 R 為當(dāng)前的回文串了南蹂。因為我們必須保證 i 在 R 里面，所以一旦有更右邊的 R 就要更新 R念恍。
此時的 P [ i ] 求出來將會是 3 六剥，P [ i ] 對應(yīng)的右邊界將是 10 + 3 = 13晚顷，所以大于當(dāng)前的 R ，我們需要把 C 更新成 i 的值疗疟，也就是 10 该默，R 更新成 13。繼續(xù)下邊的循環(huán)策彤。
public String preProcess(String s) {
int n = s.length();
if (n == 0) {
return "^$";
}
String ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.charAt(i);
ret += "#$";
return ret;
}
// 馬拉車算法
public String longestPalindrome2(String s) {
String T = preProcess(s);
int n = T.length();
int[] P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * C - i;
if (R > i) {
P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R
} else {
P[i] = 0;// 等于 R 的情況
}
// 碰到之前講的三種情況時候栓袖，需要繼續(xù)擴(kuò)展
while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
P[i]++;
}
// 判斷是否需要更新 R
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// 找出 P 的最大值
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen) / 2; //最開始講的
return s.substring(start, start + maxLen);
}
時間復(fù)雜度：for 循環(huán)里邊套了一層 while 循環(huán)，難道不是 O ( n2 )店诗，不裹刮！其實是 O（n）。我們想象一下整個過程庞瘸，首先外層有一個 for 循環(huán)捧弃，所以每個字符會遍歷一次，而當(dāng)我們擴(kuò)展的時候擦囊，每次都是從 R + 1 開始擴(kuò)展违霞，之后又會更新 R 。所以一些字符會遍歷兩次瞬场，但此時這些字符變到 R 的左邊买鸽，所以不會遍歷第三次了，因為我們每次從 R 的右邊開始擴(kuò)展泌类。綜上癞谒，每個字符其實最多遍歷 2 次，所以依舊是線性的刃榨，當(dāng)然如果字符串成為 len ，這里的 n 其實是 2 * len + 3 双仍。所以時間復(fù)雜度是 O（n）枢希。
空間復(fù)雜度：O（n）。
總結(jié)
時間復(fù)雜度從三次方降到了一次朱沃，美妙苞轿！這里兩次用到了動態(tài)規(guī)劃去求解，初步認(rèn)識了動態(tài)規(guī)劃逗物，就是將之前求的值保存起來搬卒，方便后邊的計算，使得一些多余的計算消失了翎卓。并且在動態(tài)規(guī)劃中契邀，通過觀察數(shù)組的利用情況，從而降低了空間復(fù)雜度失暴。而 Manacher 算法對回文串對稱性的充分利用坯门，不得不讓人嘆服微饥，自己加油啦！
