上一題：LeetCode第4題:findMedianSortedArrays(C語言）
寫在前面，最長公共字符串是面試中較常出現(xiàn)的題目，原因是這道題解法眾多，可對面試者進行綜合考察。
1、暴力求解
思路：雙層遍歷輸入字符串，從而窮舉出輸入字符串的所有子串，然后再用一層循環(huán)，判斷子串是否為回文字符串，思路清晰簡單，代碼略。
2、動態(tài)規(guī)劃
思路：
假設(shè)字符串s的長度為length，建立一個length*length的矩陣dp。
dp[i][j]表示“以s[i]開始s[j]結(jié)尾的回文串的長度。如果這個字符串不是回文串，讓dp[i][j]=0”。顯然，j>=i，只需往dp填j>=i的部分即可。
dp[i][j]的遞推公式可以這么表述：
（1）首先對dp的對角線元素初始化為1，也就是當(dāng)i==j時，dp[i][j]=1。
這很顯然，每個單獨的字符其實就是個長度為1的回文串。
（2）當(dāng)j-i==1：
若s[i]==s[j]，則dp[i][j]=2；否則dp[i][j]=0。
解釋：當(dāng)j-i==1時，若s[i]==s[j]，則s[i]和s[j]可以組成一個長度為2的回文串。若s[i]！=s[j]，顯然他們不可能組成回文串，dp[i][j]=0。
（3）當(dāng)j-i>=2：
若s[i]==s[j]：若dp[i+1][j-1]>0，則dp[i][j]= dp[i + 1][j - 1] + 2;否則dp[i][j]= 0;
若s[i]！=s[j]：dp[i][j]=0。
解釋：如果s[i]==s[j]，表明這個子串有可能是回文串。當(dāng)去頭去尾后它是回文串時，就可以在去頭去尾的那個回文串長度基礎(chǔ)上+2，得到它的長度。如果去頭去尾后不是回文串，那這個子串一定不是回文串，回文串長度只能是0。
若s[i]！=s[j]，顯然他們不可能組成回文串，dp[i][j]=0。
只需找到dp[i][j]的最大元素和它對應(yīng)的i和j就可以得到結(jié)果“s中最長回文子串”。
另外還有一個要注意的點：因為需要訪問dp[i+1][j-1]，因此i是從大到小的，j是從小到大的。j從0到size-1，i從j-1到0。
char * longestPalindrome(char * s){
int len = strlen(s);
if(len <= 1) return s;
int dp[len][len];
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
dp[i][j] = i == j;
}
}
int start = 0;
int max = 1;
for(int j = 1; j < len; j++){
for(int i = j - 1; i >= 0; i--){
if(s[i] == s[j]){
if(j - i == 1)
dp[i][j] = 2;
else{
if(dp[i + 1][j - 1] > 0)
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = 0;
}
}
else
dp[i][j] = 0;
if(dp[i][j] >= max) {
max = dp[i][j];
start = i;
}
}
}
char *result = (char *)malloc((max + 1) * sizeof(char));
for(int i = 0;i < max; i++){
result[i] = s[start + i];
}
result[max] = '\0';
return result;
}
3、中心擴散法
思路：遍歷輸入的字符串s，以每個字符mid為中心，分別計算mid為中心的奇數(shù)位（例如"cabac"中以"b"為中心的回文字符串）和偶數(shù)位（例如"cabbac"以"bb"為中心的回文字符串）的最長回文字符串，記錄最長回文字符串出現(xiàn)的起始下標(biāo)及長度max。
char * longestPalindrome(char * s){
int len = strlen(s);
int start = 0;
int mid = 0;
int max = 0;
int extend = 0;
while(mid < len){
//計算形如 "cabbac"以"bb"為中心的回文字符串
extend = 0;
while(mid - extend >= 0 && mid + extend + 1 < len && s[mid - extend] == s[mid + extend + 1]){
extend++;
}
if(2 * extend >= max){
max = 2 * extend;
start = mid - extend + 1;
}
//計算形如 "cabac"中以"b"為中心的回文字符串
extend = 0;
while(mid - extend - 1 >= 0 && mid + extend + 1 < len && s[mid - extend - 1] == s[mid + extend + 1]){
extend++;
}
if(2 * extend + 1 >= max){
max = 2 * extend + 1;
start = mid - extend;
}
mid++;
}
char *result = (char *)malloc((max + 1) * sizeof(char));
for(int i = 0;i < max; i++){
result[i] = s[start + i];
}
result[max] = '\0';
return result;
}
4、中心擴散的改進算法
思路：中心擴散思路中，需要計算mid為中心的奇數(shù)位（例如"cabac"中以"b"為中心的回文字符串）和偶數(shù)位（例如"cabbac"以"bb"為中心的回文字符串）的最長回文字符串，現(xiàn)將輸入的字符串左右填充特殊字符，即將輸入字符"babacd"每兩個字符之間分別填充字符""，變?yōu)?babbad"，可將所有字符均變?yōu)槠鏀?shù)個長度，從而避免了奇數(shù)位和偶數(shù)位分別判斷，但該方法需要額外申請內(nèi)存存儲填充字符串，時間上并沒有快，但可為后續(xù)時間復(fù)雜度為O(n)的方法提供思路。
char * longestPalindrome(char * s){
int len = strlen(s);
int new_len = 2 * len + 1;
char *new_s = (char *)malloc((new_len + 1) * sizeof(char));
int j = 0;
for(int i = 0; i < len; i++){
new_s[j++] = '*';
new_s[j++] = s[i];
}
new_s[j] = '*';
new_s[new_len] = '\0';
int start = 0;
int mid = 1;
int max = 0;
int extend = 0;
while(mid < new_len){
extend = 0;
while(mid - extend - 1 >= 0 && mid + extend + 1 < new_len && new_s[mid - extend - 1] == new_s[mid + extend + 1]){
extend++;
}
if(2 * extend + 1 >= max){
max = 2 * extend + 1;
start = mid - extend;
}
mid += 1;
}
char *result = (char *)malloc((max / 2 + 1) * sizeof(char));
for(int i = 0; i < max / 2; i++){
result[i] = new_s[start + 1 + 2 * i ];
}
result[max / 2] = '\0';
return result;
}
本系列文章，旨在打造LeetCode題目解題方法，幫助和引導(dǎo)同學(xué)們開闊學(xué)習(xí)算法思路，由于個人能力和精力的局限性，也會參考其他網(wǎng)站的代碼和思路，如有侵權(quán)，請聯(lián)系本人刪除。
