問題描述
給定一個(gè)字符串 s，找出其中最長的回文子串，假設(shè)給定字符串的長度最大維 1000.
例如:
輸入: "babad"
輸出: "bab"
注意： “aba” 也是正確的解，有多個(gè)解返回其中一個(gè)即可
輸入："cbbd"
輸出："bb"
回文串是指一個(gè)字符串對稱，從最左邊和最右邊分別往最中間遍歷，各個(gè)位置的字符都相同。解決這個(gè)問題，下面將從四個(gè)算法分別進(jìn)行介紹。
1、暴力枚舉法（不可?。?/strong>
暴力枚舉法是最簡單、最容易想到的方法，其思路是：首先找到字符串 s 的所有子串，然后判斷該子串是否是回文字符串，最后返回最長的回文子串。該方法雖然簡單明了，但因其計(jì)算成本太高，該算法在實(shí)際中并不可取。
由于一個(gè)長為 n 的字符串，共有 $\frac{n(n+1)}{2}$ 個(gè)連續(xù)子串，故尋找子串的時(shí)間復(fù)雜度為 $O(n^2)$, 判斷一個(gè)字符串是否維回文串的時(shí)間復(fù)雜度維 $O(n)$,故
時(shí)間復(fù)雜度: $O(n^3)$
空間復(fù)雜度為: $O(1)$。
下面是 Java 的實(shí)現(xiàn)代碼：
public class LongestPalindromicSubstring {
public String longestPalindrome(String s) {
// 保存得到的最長回文子串的起始位置
int left = 0, right = 0;
int len = s.length();
for (int i=0; i<len; ++i) {
for (int j=i; j<len; ++j) {
// 獲取 s 的連續(xù)子串
String subStr = s.substring(i, j+1);
// 判斷子串是否是回文字符串
if (isPalindrome(subStr)) {
if (j-i > right-left) {
left = i;
right = j;
}
}
}
}
return s.substring(left, right+1);
}
private boolean isPalindrome(String s) {
int len = s.length();
int left = 0, right = len-1;
while (left < right) {
if (s.charAt(left) != s.charAt(right))
return false;
++left;
--right;
}
return true;
}
}
2、中心擴(kuò)展法（可?。?/strong>
中心擴(kuò)展法是根據(jù)暴力枚舉法改進(jìn)而來，主要是去除了一些不必要的子字符串的判斷，主要思路:首先從字符串 s 中選擇一個(gè)字符作為子字符串的中心字符,然后以該字符維中心依次往左右兩邊擴(kuò)展,判斷該子串的最左邊和最右邊的字符是否相同,相同則繼續(xù)向兩邊擴(kuò)展,不相同則停止擴(kuò)展,該子串則是以該字符為中心的最長回文子串,這樣就減少了很多在暴力枚舉方法中不必要的字符的判斷.
和暴力枚舉方法比較,以"abacdfgdcaba"為例,假設(shè)我們以第一個(gè)字符 'c' 為中心,中心擴(kuò)展首先比較"acd",由于 'a' 和 'd'不相同,則停止擴(kuò)展,二暴力枚舉還需比較 "bacdf" 和 "abacdfg".該算法在擴(kuò)展時(shí)需要同時(shí)考慮子串是奇數(shù)和偶數(shù)的情況.
由于需要依次迭代每個(gè)字符串中心,因此該迭代需要 $O(n)$ 時(shí)間復(fù)雜度,同時(shí)從中心向兩邊擴(kuò)展的復(fù)雜度維 $O(n)$,因此:
時(shí)間復(fù)雜度: $O(n^2)$
空間復(fù)雜度為: $O(1)$。
public class LongestPalindromicSubstring {
public static void main(String[] args) {
System.out.println(new test().longestPalindrome("abacdfgdcaba"));
System.out.println(new test().longestPalindrome("cbbd"));
System.out.println(new test().longestPalindrome("babad"));
}
public String longestPalindrome(String s) {
// 保存獲得的最大回文子串
String maxStr = "";
int len = s.length();
for(int i=0; i<len; ++i) {
String subStr1 = isPalindrome(s, i, i);
if (subStr1.length() > maxStr.length()) {
maxStr = subStr1;
}
String subStr2 = isPalindrome(s, i, i+1);
if (subStr2.length() > maxStr.length()) {
maxStr = subStr2;
}
}
return maxStr;
}
private String isPalindrome(String s, int i, int j) {
// i 表示中心擴(kuò)展的左邊字符
// j 表示中心擴(kuò)展的右邊字符
int len = s.length();
while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
--i;
++j;
}
return s.substring(i+1, j);
}
}
3、動(dòng)態(tài)規(guī)劃（可?。?/strong>
回文字符串的子串也是回文字符串,我們可以將最長回文子串分解為一些列子問題,使用動(dòng)態(tài)規(guī)劃.設(shè) f 為狀態(tài)表,f(i,j)表示字符區(qū)間 [i, j](包括j)是否為回文字符串
,f(i, j)=false 表示子串 [i, j] 不是回文字符串,f(i, j)=true 表示子串 [i, j] 為回文字符串.當(dāng)我們判斷了字符 [i], [j] 相同時(shí),只需判斷 f(i+1, j-1) 是否維 true 即可.
狀態(tài)表滿足以下關(guān)系:
由于狀態(tài)表 f 是一個(gè) n*n 的方陣,且是一個(gè)對稱方陣,故我們只需判斷狀態(tài)表 f 的右上角的內(nèi)容,因此:
時(shí)間復(fù)雜度: $O(n^2)$
空間復(fù)雜度: $O(n^2)$
實(shí)現(xiàn)代碼:
public class test {
public static void main(String[] args) {
System.out.println(new test().longestPalindrome("abacdfgdcaba"));
System.out.println(new test().longestPalindrome("cbbd"));
System.out.println(new test().longestPalindrome("babad"));
}
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] f = new boolean[n][n];
int left =0, right=0;
for (int j=0; j<n; ++j) {
f[j][j] = true;
for (int i=0; i<j; ++i) {
if (s.charAt(i) == s.charAt(j) && (i == j-1 || f[i+1][j-1])) {
if (j-i > right - left) {
left = i;
right = j;
}
f[i][j] = true;
}
}
}
return s.substring(left, right+1);
}
}
該代碼首先將狀態(tài)表全部初始化為 false, 然后按照從上到下,從左到右的順序依次判斷狀態(tài)表的值.
4、Manacher 算法（馬拉車算法）（可?。?/strong>
Manacher 算法是一種經(jīng)典的求取最長回文子串的方法,其基本原理是使用已知回文字符串的左半部分來推導(dǎo)以右半部分的字符為中心的回文字符.
我們使用 p[i] 表示以第 i 個(gè)字符為中心的最長回文半徑.可以利用已知p[0],p[1]......p[i-1]的值,來計(jì)算 p[i] 的值.我們定義 maxRight 是當(dāng)前計(jì)算 i 位置時(shí)所有回文子串所能達(dá)到的最右端的位置,且該回文串的中心位置為 k,此時(shí)有如下關(guān)系: maxRight = k + p[k],此時(shí)有兩種情況:
第一種情況:i > maxRight,此時(shí)初始化p[i] = 1, 然后判斷s[i+p[i]] == s[i-p[i]],若不相等則停止,若相等,則++p[i]
if (i > maxRight) {
p[i] = 1;
while(s[i+p[i]] == s[i-p[i]]) {
++p[i];
}
}
第二種情況:i <= maxRight,此時(shí)不在給 p[i] 賦值維為1,由回文串的對稱性可得, 2k-i 是 i 關(guān)于 k 的對稱點(diǎn).此時(shí)由兩種情況:
- 以 2k-i 為中心的回文串的半徑(如圖藍(lán)色箭頭)大于等于 $maxRight - i$(空心箭頭),由對稱性可知,已知紫色箭頭 5 和 6 關(guān)于 k 對稱,且 2k-i 和 i 關(guān)于 k 對稱,所以空心箭頭 1 和 4 對稱,2 和 3 對稱,又箭頭 7 和 8 對稱,且箭頭 1 和 2 分別是 7 和 8 的一部分,所以空心箭頭 1 和 2 對稱,故空心箭頭 3 和 4 對稱.所以p[i]的對稱半徑至少為 maxRight - i.所以首先 p[i]=maxRight - i,然后在依次往兩邊擴(kuò)展判斷是否對稱.
- 以 2k-i 為中心的回文半徑小于 maxRight-i,根據(jù)和上面類似的推導(dǎo),可以得知 p[i] = p[2k-i],且不在擴(kuò)展.
復(fù)雜度分析:
- 時(shí)間復(fù)雜度:$O(n)$
- 空間復(fù)雜度: $O(n)$
public class test {
public static void main(String[] args) {
System.out.println(new test().longestPalindrome("abacdfgdcaba"));
System.out.println(new test().longestPalindrome("cbbd"));
System.out.println(new test().longestPalindrome("babad"));
}
public String longestPalindrome(String s) {
StringBuilder temp = new StringBuilder("#");
for (int i = 0; i < s.length(); ++i) {
temp.append(s.charAt(i));
temp.append("#");
}
String str = temp.toString();
/*
* maxCenter: 保存當(dāng)前能延伸到最右端的回文字符串的中心位置
* maxId: 保存當(dāng)前最長回文子串的中心位置
* p: 保存以該位置的字符維中心位置的最長回文字符的右邊長度
*/
int maxCenter=0, maxId=0;
int n = str.length();
int[] p = new int[n];
for (int i=0; i<n; ++i) {
int syncCenter = 2 * maxCenter - i;
p[i] = (i<maxCenter + p[maxCenter) ? Math.min(p[syncCenter], maxCenter + p[maxCenter] - i) : 1;
while(i-p[i] >=0 && i+p[i]<n && str.charAt(i-p[i]) == str.charAt(i+p[i])) {
++p[i];
}
if (i + p[i] >= p[maxCenter] + maxCenter) {
maxCenter = i;
}
if (p[i] > p[maxId]) {
maxId = i;
}
}
return s.substring((maxId - p[maxId])/2, (maxId + p[maxId]) / 2);
}
}
