給定一個(gè)字符串 s税朴，找到 s 中最長的回文子串宛渐。你可以假設(shè) s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案弓坞。
示例 2：
輸入: "cbbd"
輸出: "bb"
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有饿凛。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處剖笙。
解法一：暴力解法
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;
}
時(shí)間復(fù)雜度：兩層 for 循環(huán) O（n2），for 循環(huán)里邊判斷是否為回文请唱，O（n）弥咪，所以時(shí)間復(fù)雜度為 O（n3）。
空間復(fù)雜度：O（1）十绑，常數(shù)個(gè)變量聚至。
解法二 ：最長公共子串
求兩個(gè)字符串的最長公共子串 參考：https://blog.csdn.net/u010397369/article/details/38979077
問題：有兩個(gè)字符串str和str2，求出兩個(gè)字符串中最長公共子串長度本橙。
比如：str=acbcbcef扳躬，str2=abcbced，則str和str2的最長公共子串為bcbce甚亭，最長公共子串長度為5贷币。
算法思路：
1、把兩個(gè)字符串分別以行和列組成一個(gè)二維矩陣亏狰。
2役纹、比較二維矩陣中每個(gè)點(diǎn)對(duì)應(yīng)行列字符中否相等，相等的話值設(shè)置為1暇唾，否則設(shè)置為0促脉。
3、通過查找出值為1的最長對(duì)角線就能找到最長公共子串策州。
針對(duì)于上面的兩個(gè)字符串我們可以得到的二維矩陣如下：
從上圖可以看到瘸味，str和str2共有5個(gè)公共子串，但最長的公共子串長度為5够挂。
為了進(jìn)一步優(yōu)化算法的效率旁仿，我們可以再計(jì)算某個(gè)二維矩陣的值的時(shí)候順便計(jì)算出來當(dāng)前最長的公共子串的長度，即某個(gè)二維矩陣元素的值由item[i][j]=1演變?yōu)閕tem[i][j]=1 +item[i-1][j-1]下硕，這樣就避免了后續(xù)查找對(duì)角線長度的操作了丁逝。修改后的二維矩陣如下：
代碼實(shí)現(xiàn)
/**
* 獲取兩個(gè)字符串最長公共子串長度
* @param str 第一個(gè)字符串
* @param str2 第二個(gè)字符串
* @return 如果存在則返回最長公共子串長度，否則返回0
*/
public static int getLCSLength(String str, String str2){
char[] ary = str.toCharArray();
char[] ary2 = str2.toCharArray();
int[][] temp = new int[ary.length][ary2.length]; //聲明一個(gè)二維數(shù)組梭姓，存儲(chǔ)最長公共子串長度
int length = 0; //最長公共子串長度
for (int i = 0; i < ary.length; i++) {
for (int j = 0; j < ary2.length; j++) {
if(ary[i] == ary2[j]){
if(i > 0 && j > 0){
temp[i][j] = temp[i-1][j-1] + 1;
}else{
temp[i][j] = 1;
}
if(temp[i][j] > length){ //當(dāng)前元素值大于最大公共子串長度
length = temp[i][j];
}
}else{
temp[i][j] = 0;
}
}
}
return length;
}
再看一個(gè)例子霜幼，S = "abc435cba"，S’ = "abc534cba" 誉尖，最長公共子串是 "abc" 和 "cba" 罪既，但很明顯這兩個(gè)字符串都不是回文串。
所以我們求出最長公共子串后，并不一定是回文串琢感，我們還需要判斷該字符串倒置前的下標(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)然我們不需要每個(gè)字符都判斷，我們只需要判斷末尾字符就可以苛蒲。
首先 i 卤橄，j 始終指向子串的末尾字符。所以 j 指向的紅色的 a 倒置前的下標(biāo)是 beforeRev = length - 1 - j = 4 - 1 - 2 = 1臂外，對(duì)應(yīng)的是字符串首位的下標(biāo)窟扑，我們還需要加上字符串的長度才是末尾字符的下標(biāo)，也就是 beforeRev + arr[ i ] [ j ] - 1 = 1 + 3 - 1 = 3漏健，因?yàn)?arr[ i ] [ j ] 保存的就是當(dāng)前子串的長度嚎货，也就是圖中的數(shù)字 3 。此時(shí)再和它與 i 比較蔫浆，如果相等厂抖，則說明它是我們要找的回文串。
之前的 S = "abc435cba"克懊，S' = "abc534cba" 忱辅，可以看一下圖示，為什么不符合谭溉。
當(dāng)前 j 指向的 c 墙懂，倒置前的下標(biāo)是 beforeRev = length - 1 - j = 9 - 1 - 2 = 6，對(duì)應(yīng)的末尾下標(biāo)是 beforeRev + arr[ i ] [ j ] - 1 = 6 + 3 - 1 = 8 扮念，而此時(shí) 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)是否對(duì)應(yīng)
maxLen = arr[i][j];
maxEnd = i;
}
/*************************************/
}
}
return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
}
時(shí)間復(fù)雜度：兩層循環(huán)，O（n2）颅悉。
空間復(fù)雜度：一個(gè)二維數(shù)組，O（n2）迁匠。
空間復(fù)雜度其實(shí)可以再優(yōu)化一下剩瓶。
我們分析一下循環(huán)驹溃，i = 0 ，j = 0延曙，1豌鹤，2 ... 8 更新一列，然后 i = 1 枝缔，再更新一列布疙，而更新的時(shí)候我們其實(shí)只需要上一列的信息，更新第 3 列的時(shí)候愿卸，第 1 列的信息是沒有用的拐辽。所以我們只需要一個(gè)一維數(shù)組就可以了。但是更新 arr [ i ] 的時(shí)候我們需要 arr [ i - 1 ] 的信息擦酌，假設(shè) a [ 3 ] = a [ 2 ] + 1，更新 a [ 4 ] 的時(shí)候菠劝， 我們需要 a [ 3 ] 的信息赊舶，但是 a [ 3 ] 在之前已經(jīng)被更新了，所以 j 不能從 0 到 8 赶诊，應(yīng)該倒過來笼平，a [ 8 ] = a [ 7 ] + 1，a [ 7 ] = a [ 6 ] + 1 , 這樣更新 a [ 8 ] 的時(shí)候用 a [ 7 ] 舔痪，用完后才去更新 a [ 7 ]寓调，保證了不會(huì)出錯(cuò)。
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);
}
時(shí)間復(fù)雜度：O（n2）滋捶。
空間復(fù)雜度：降為 O（n）痛悯。
