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 算法對回文串對稱性的充分利用坯门,不得不讓人嘆服微饥,自己加油啦!