給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。示例 1： 輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個有效答案

首先，看懂題目很重要！！！啥是回文？

把相同的詞匯或句子 [1] ，在下文中調(diào)換位置或顛倒過來，產(chǎn)生首尾回環(huán)的情趣，叫做回文，也叫回環(huán)。

這道題對時間復雜度沒有要求，可即便如此，剛開始還是毫無辦法 ╮(╯-╰)╭。想了一會兒，遍歷吧，俗稱暴力法，畢竟解決問題最要緊，優(yōu)化可以繼續(xù)搞。通過簡單分析可以知道，回文的字符串兩兩對應相等。假設長度為n的回文字符串，滿足如下條件

s[i] == s[n-i-1]

?我們遍歷給定字符串的每一個字符，找到以它開始的最長回文字符串。對于給定的起始字符，考慮最長，我們肯定是從字符串末尾從后往前遍歷，使用first, last兩個指針分別指向首尾，遍歷直到first > last則結(jié)束遍歷，這時候保留得到的長度和起始位置。開始下一個字符遍歷。

隨著遍歷的過程中，我們可以發(fā)現(xiàn)上述的暴力法是可以優(yōu)化的，舉個例子，s[ i ] 的最長回文子串尾指針為s[ j ],當我們遍歷i下一個元素 s[ i + 1]的時候，我們通過上一步可以直到s[ i + 1] 和 s[ j - 1 ]是回文的，所以只需要遍歷 j+1 ~ last 這段區(qū)間即可。同理，對于后續(xù)的每個元素我們都可以這樣做，只需要從末尾元素遍歷到先前最近的回文字符即可。假設對于每個起始字符 first[ i ]，它對應的最長回文子串尾字符為 last[ i ], 當我們繼續(xù)遍歷首字符 first[j]（i < j < n）時，只需要遍歷MAX（last[0], last[1]...last[j -1]）到n的區(qū)間即可。這樣可以節(jié)省一點不必要的操作。思想和滑動窗口解決無重復最長子串問題一樣。

char * longestPalindrome(char * s){int first, last, len = 0, i, j, max = 0, cursor, jump = 0;char *ps = s;if (!s)return s;while(*ps++ != '\0')len++;//遍歷每個字符for (i = 0; i < len; i++){for (j = len - 1; j >= jump; j--){first = i, last = j;while (first <= last){if (s[first++] != s[last--])break;}if (s[first-1] == s[last+1]){if (j - i + 1 > max){max = j - i + 1;cursor = i;}//jump表示可以省略的位置，i后面的元素不用再與jump左邊的元素比較 //和滑動窗口思想一樣。jump = jump > last + 1 ? jump: (last + 1);break;} }}ps = s + cursor;if (max < len)ps[max] = '\0';return ps; }

暴力遍歷法時間復雜度為O(n^3)，中心擴展方法時間復雜度為O(n^2)，這個方法其實是相當簡單的。如果說暴力遍歷回文串方向是從兩端匹配到中間的話，中心擴展方向是從中心到兩端。這里中心有2N-1個，包括奇數(shù)中心N和偶數(shù)中心N-1。中心擴展方法即從中心向兩端遍歷，遇到不匹配則退出。

#define MAX(a,b) ((a)>(b)?(a):(b)) int centerExpand(char *s, int len, int left, int right) {while(left >= 0 && right < len && s[left] == s[right]){left--;right++;}return right - left - 1; }char * longestPalindrome(char * s){int len = 0, center = 0, max = 0, max0 = 0, max1 = 0, cursor = 0;char *pStr = s;if (!s)return s;while (*pStr++ != '\0')len++;for (center = 0; center < len; center++){max0 = centerExpand (s, len, center, center);max1 = centerExpand (s, len, center, center+1);if (max < max0 || max < max1){if (max0 > max1)cursor = center - max0 / 2;elsecursor = center + 1 - max1 /2;max = MAX(max0, max1);}}pStr = s + cursor;if (max != len)pStr[max] = '\0';return pStr; }

第三種是動態(tài)規(guī)劃，這個等我學會再寫出來。

=========================================================================================

動態(tài)規(guī)劃的基本步驟可分為：

1. 分階段

2. 狀態(tài)遞推方程

3. 求最優(yōu)解。

這道題如果使用動態(tài)規(guī)劃，顯然要使用m[i][j]類型，假設i和j分別表示字符的位置，m[i][j]表示字符i到j是否為回文字符串。如果是的話m[i][j] = 1; 否則 m[i][j] = 0; 遞推方程為m[i][j] = m[i+1][j-1] && (s[i] == s[j]) ; 我們可以先算出長度為1和2的m[][]值，

m[i][i] = 1; m[i][i+1] = (s[i] == s[i+1]);接著遞推，在遞推過程中，可以記錄最長回文字符串值max = j - i + 1;起點為i.

難度不大，就是不容易想到，平常使用動態(tài)規(guī)劃的時候m[i][j]用來表示最優(yōu)解，本題只保存了狀態(tài)。需要多多練習。

下面是動態(tài)規(guī)劃的c代碼：

char * longestPalindrome(char * s){int i,j,d, len = 0, m[1001][1001]={0}, max = 1, c = 0;char *pStr = s;if (!s)return s;while (*pStr++ != '\0')len++;if (len <= 1)return s;//初始化邊界，單字母回文和雙字母回文for (i = 0; i < len - 1; i++){m[i][i] = 1;if (s[i] == s[i+1]){m[i][i+1] = 1;if (max < 2){max = 2;c = i;} } elsem[i][i+1] = 0;} m[i][i] = 1;//遞推，查詢3字母到n-1字母長度for (d = 2; d < len; d++)for (i = 0; i + d < len; i++){j = d + i;m[i][j] = (m[i+1][j-1]) && (s[i] == s[j]);if (m[i][j] && (j-i+1) > max){max = j - i + 1; c = i;}}s = s + c;s[max] = '\0';return s; }

=============================================================================================

Linux應用程序、內(nèi)核、驅(qū)動、后臺開發(fā)交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。
?

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的leetcode 5. 最长回文子串 暴力法、中心扩展算法、动态规划，马拉车算法(Manacher Algorithm)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。