Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
題目簡介
這道題輸入是一個(gè)字符串尿褪，要求輸出最長的回文子串凉倚。
知識要點(diǎn)
- 動態(tài)規(guī)劃的思想
- 對稱的思想
解題思路
Approach 1: Brute Force
暴力法應(yīng)該是最樸素的算法了：我們查找所有的子串搏熄，判斷是否為回文并記錄最長回文子串腾它。這種算法筆者在此不列代碼注暗。
關(guān)于時(shí)間復(fù)雜度，尋找所有子串為O(n2)，判斷是否為回文為O(n)滚局，所以總的時(shí)間復(fù)雜度為O(n3)。
Approach 2: Dynamic Programming
這道題應(yīng)用動態(tài)規(guī)劃來解題應(yīng)該還是很容易想到的顽频。設(shè)置一個(gè)dp布爾型二維數(shù)組藤肢，其中dp[i][j]表示字符串從第i位置到第j位置（包括i,j）是否為回文。那么很容易得到狀態(tài)轉(zhuǎn)移方程：<code>if ( dp[i+1][j-1] == true && s[i] == s[j] ) dp[i][j] = true;</code> dp數(shù)組初始化操作見代碼中pre-process部分糯景。
c++代碼如下：
class Solution {
public:
//dynamic programming
string longestPalindrome(string s) {
int len = s.length();
bool dp[1010][1010] = {0};
int i, j;
int maxL=1, start=0, tmpL;
//pre-processing
for (i=0; i<len; ++i){
dp[i][i] = true;
j = i + 1;
if (j < len && s[i] == s[j]){
dp[i][j] = true;
maxL = 2;
start = i;
}
}
//dynamic programming
for (tmpL=3; tmpL<=len; ++tmpL){
for (i=0; i+tmpL-1<len; ++i){
j = i+tmpL-1;
if (dp[i+1][j-1] && s[i]==s[j]){
dp[i][j] = true;
maxL = tmpL;
start = i;
}
}
}
//output
string lp = s.substr(start, maxL);
return lp;
}
};
時(shí)間復(fù)雜度為O(n^2)
Approach 3: Expand Around Center
第三種算法被稱為中心擴(kuò)展法嘁圈。核心思想為：從左到右遍歷字符串，從“中心”向兩邊擴(kuò)展直到不再是回文蟀淮。該算法要注意的是“中心”的選擇：有兩種情況最住，“aba”和“abba”。前者中心為一個(gè)字符怠惶，后者中心為兩個(gè)字符涨缚。我們對兩種情況分別進(jìn)行處理。
C++代碼如下：
class Solution {
public:
//expand around center
string longestPalindrome(string s) {
int len = s.length();
int maxL = 1, start = 0, tmpL;
int i, j, k;
//aba type
for (i=0; i<len; ++i){
j = i-1;
k = i+1;
tmpL = 1;
while(j>=0 && k<len && s[j]==s[k]){
tmpL += 2;
if (tmpL > maxL){
maxL = tmpL;
start = j;
}
j--;
k++;
}
}
//abba type
for (i=0; i<len; ++i){
j = i;
k = i+1;
tmpL = 0;
while(j>=0 && k<len && s[j]==s[k]){
tmpL += 2;
if (tmpL > maxL){
maxL = tmpL;
start = j;
}
j--;
k++;
}
}
//output
string lp = s.substr(start, maxL);
return lp;
}
};
時(shí)間復(fù)雜度為O(n^2)
Approach 4: Manacher's Algorithm
這個(gè)算法算是一個(gè)比較冷門的算法了策治。不過其思想非常有趣脓魏，還是很有理解透徹的價(jià)值的。網(wǎng)上的眾多文章對該算法的解釋并不是很清晰通惫，筆者覺得manacher's algorithm這篇文章算是解釋最好的一篇了茂翔，轉(zhuǎn)過來參考一下。
筆者依據(jù)該算法的思想自己用C++實(shí)現(xiàn)了一下：
class Solution {
public:
//manacher's algorithm
//add # to the string
string pre_process(string s){
string pps = "#";
for (int i=0; i<s.length(); ++i){
pps += s.substr(i, 1);
pps += "#";
}
return pps;
}
//find the maximum value in p[], which is the radius of the longest palindrome. Return the palindromic string.
string post_process(string s, int p[], int n){
int center, radius=0;
for (int i=0; i<n; ++i){
if (p[i] > radius){
radius = p[i];
center = i;
}
}
string ans = "";
for (int i=center-radius; i<=center+radius; ++i){
if (s[i] != '#')
ans += s.substr(i, 1);
}
return ans;
}
string longestPalindrome(string s){
s = pre_process(s);
int p[2010]; //the radius of palindromic substring, not including character in i
int maxlen = 0, maxi = 0;
p[0] = 0;
//different situations of manacher's algorithm
for (int i=1; i<s.length(); ++i){
// i >= maxlen, the point is out of the range
if (i >= maxlen){
p[i] = 0;
while ( i-(p[i]+1)>=0 && i+(p[i]+1)<s.length() && s[i-(p[i]+1)] == s[i+(p[i]+1)] )
++p[i];
if (i+p[i] > maxlen){
maxi = i;
maxlen = maxi+p[i];
}
}
// i < maxlen, the point is within the range
else{
int j = 2*maxi - i; // the symmetric point
if (j - p[j] < maxi - p[maxi])
p[i] = maxlen - i;
else if (j - p[j] > maxi - p[maxi])
p[i] = p[j];
else{
p[i] = p[j];
while ( i-(p[i]+1)>=0 && i+(p[i]+1)<s.length() && s[i-(p[i]+1)] == s[i+(p[i]+1)] )
++p[i];
if (i+p[i] > maxlen){
maxi = i;
maxlen = maxi+p[i];
}
}
}
}
string ansstr = post_process(s, p, s.length());;
return ansstr;
}
};
該算法時(shí)間復(fù)雜度達(dá)到了O(n)
對代碼的一些說明：
- pre-process函數(shù)是為字符串沒個(gè)字符之間添加‘#’履腋，使得“aba”型和“abba”型能夠統(tǒng)一處理珊燎。
- post-process函數(shù)是輸出處理。尋找最大回文半徑遵湖，并將‘#’刪除掉俐末。返回最終的輸出。
- 算法的主體部分的思想?yún)⒖?a target="_blank" rel="nofollow">manacher's algorithm這篇文章奄侠。
