給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"
解題思路
解法一：動態(tài)規(guī)劃法
（一）狀態(tài)
f[i][j]表示s的第 i 個字符到第 j 個字符組成的子串，是否為回文串
（二）轉(zhuǎn)移方程
如果s的第 i 個字符和第 j 個字符相同的話，且 i + 1, 到 j - 1 的子串也是回文串的話，f[i][j] 也為回文串
f[i][j] = f[i + 1][j - 1] and s[i] == s[j]
稍微要注意的是，如果 i == j 或者 i + 1 == j 的時候，也就是單個字符的子串和兩個相鄰字符的子串，就不需要f[i + 1][j - 1]了
如果s的第 i 個字符和第 j 個字符不同的話，f[i][j] 不是回文串
然后注意遍歷順序，i 從最后一個字符開始往前遍歷，j 從 i 開始往后遍歷，這樣可以保證每個子問題都已經(jīng)算好了
代碼如下：
public String longestPalindrome(String s) {
String res = "";
int n = s.length();
boolean[][] f = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if(s.charAt(i) == s.charAt(j) && (j - i <= 1 || f[i + 1][j - 1])) {
f[i][j] = true;
if(j - i >= res.length()){
res = s.substring(i, j + 1);
}
}
}
}
return res;
}
解法二：中心擴展法
思路
回文串一定是對稱的
每次選擇一個中心，進行中心向兩邊擴展比較左右字符是否相等
中心點的選取有兩種
aba，中心點是b
aa，中心點是兩個a之間
所以共有兩種組合可能
left：i，right：i
left：i，right：i+1
public class Solution2020106 {
public int n;
public String s;
// 中心擴展法
private int centerExpend(int left,int right) {
while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
return right - left - 1;
}
public String longestPalindrome (String zifu) {
this.s=zifu;
if( s.length() < 2){
return s;
}
int start = 0,end = 0;
n = s.length();
for(int i = 0;i < n;i++){
int len1 = centerExpend(i,i);
int len2 = centerExpend(i,i+1);
// 兩種組合取最大回文串的長度
int maxLen = Math.max(len1,len2);
if(maxLen > end - start){
// 更新最大回文串的首尾字符索引
start = i - ((maxLen - 1) >>>1);
end = i + (maxLen >>> 1);
}
}
return s.substring(start,end+1);
}
public static void main(String[] args) {
Solution2020106 so=new Solution2020106();
System.out.println(so.longestPalindrome("abayuioppoiuy"));
}
}
圖解
var longestPalindrome = function(s) {
if(!s || s.length < 2){
return s;
}
let start = 0,end = 0;
let n = s.length;
// 中心擴展法
let centerExpend = (left,right) => {
while(left >= 0 && right < n && s[left] == s[right]){
left--;
right++;
}
return right - left - 1;
}
for(let i = 0;i < n;i++){
let len1 = centerExpend(i,i);
let len2 = centerExpend(i,i+1);
// 兩種組合取最大回文串的長度
let maxLen = Math.max(len1,len2);
if(maxLen > end - start){
// 更新最大回文串的首尾字符索引
start = i - ((maxLen - 1) >> 1);
end = i + (maxLen >> 1);
}
}
return s.substring(start,end+1);
};
方法三：超級詳解動態(tài)規(guī)劃
“動態(tài)規(guī)劃”的方法是非常重要算法思想，并且這道題也是很經(jīng)典的動態(tài)規(guī)劃問題，一些快速判斷子串是否是回文的問題都以這道問題為基礎。
解決這類 “最優(yōu)子結(jié)構(gòu)” 問題，可以考慮使用 “動態(tài)規(guī)劃”：
1、定義 “狀態(tài)”；
2、找到 “狀態(tài)轉(zhuǎn)移方程”。
記號說明： 下文中，使用記號 s[l, r] 表示原始字符串的一個子串，l、r 分別是區(qū)間的左右邊界的索引值，使用左閉、右閉區(qū)間表示左右邊界可以取到。舉個例子，當 s = 'babad' 時，s[0, 1] = 'ba' ，s[2, 4] = 'bad'。
1、定義 “狀態(tài)”，這里 “狀態(tài)”數(shù)組是二維數(shù)組。
dp[l][r] 表示子串 s[l, r]（包括區(qū)間左右端點）是否構(gòu)成回文串，是一個二維布爾型數(shù)組。即如果子串 s[l, r] 是回文串，那么 dp[l][r] = true。
2、找到 “狀態(tài)轉(zhuǎn)移方程”。
首先，我們很清楚一個事實：
1、當子串只包含 1 個字符，它一定是回文子串；
2、當子串包含 2 個以上字符的時候：如果 s[l, r] 是一個回文串，例如 “abccba”，那么這個回文串兩邊各往里面收縮一個字符（如果可以的話）的子串 s[l + 1, r - 1] 也一定是回文串，即：如果 dp[l][r] == true 成立，一定有 dp[l + 1][r - 1] = true 成立。
根據(jù)這一點，我們可以知道，給出一個子串 s[l, r] ，如果 s[l] != s[r]，那么這個子串就一定不是回文串。如果 s[l] == s[r] 成立，就接著判斷 s[l + 1] 與 s[r - 1]，這很像中心擴散法的逆方法。
事實上，當 s[l] == s[r] 成立的時候，dp[l][r] 的值由 dp[l + 1][r - l] 決定，這一點也不難思考：當左右邊界字符串相等的時候，整個字符串是否是回文就完全由“原字符串去掉左右邊界”的子串是否回文決定。但是這里還需要再多考慮一點點：“原字符串去掉左右邊界”的子串的邊界情況。
1、當原字符串的元素個數(shù)為 3 個的時候，如果左右邊界相等，那么去掉它們以后，只剩下 1 個字符，它一定是回文串，故原字符串也一定是回文串；
2、當原字符串的元素個數(shù)為 2 個的時候，如果左右邊界相等，那么去掉它們以后，只剩下 0 個字符，顯然原字符串也一定是回文串。
把上面兩點歸納一下，只要 s[l + 1, r - 1] 至少包含兩個元素，就有必要繼續(xù)做判斷，否則直接根據(jù)左右邊界是否相等就能得到原字符串的回文性。而“s[l + 1, r - 1] 至少包含兩個元素”等價于 l + 1 < r - 1，整理得 l - r < -2，或者 r - l > 2。
綜上，如果一個字符串的左右邊界相等，以下二者之一成立即可：
1、去掉左右邊界以后的字符串不構(gòu)成區(qū)間，即“ s[l + 1, r - 1] 至少包含兩個元素”的反面，即 l - r >= -2，或者 r - l <= 2；
2、去掉左右邊界以后的字符串是回文串，具體說，它的回文性決定了原字符串的回文性。
于是整理成“狀態(tài)轉(zhuǎn)移方程”：
dp[l, r] = (s[l] == s[r] and (l - r >= -2 or dp[l + 1, r - 1]))
或者
dp[l, r] = (s[l] == s[r] and (r - l <= 2 or dp[l + 1, r - 1]))
編碼實現(xiàn)細節(jié)：因為要構(gòu)成子串 l 一定小于等于 r ，我們只關心 “狀態(tài)”數(shù)組“上三角”的那部分取值。理解上面的“狀態(tài)轉(zhuǎn)移方程”中的 (r - l <= 2 or dp[l + 1, r - 1]) 這部分是關鍵，因為 or 是短路運算，因此，如果收縮以后不構(gòu)成區(qū)間，那么就沒有必要看繼續(xù) dp[l + 1, r - 1] 的取值。
讀者可以思考一下：為什么在動態(tài)規(guī)劃的算法中，不用考慮回文串長度的奇偶性呢。想一想，答案就在狀態(tài)轉(zhuǎn)移方程里面。
具體編碼細節(jié)在代碼的注釋中已經(jīng)體現(xiàn)。
參考代碼 ：
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len <= 1) {
return s;
}
int longestPalindrome = 1;
String longestPalindromeStr = s.substring(0, 1);
boolean[][] dp = new boolean[len][len];
// abcdedcba
// l r
// 如果 dp[l, r] = true 那么 dp[l + 1, r - 1] 也一定為 true
// 關鍵在這里：[l + 1, r - 1] 一定至少有 2 個元素才有判斷的必要
// 因為如果 [l + 1, r - 1] 只有一個元素，不用判斷，一定是回文串
// 如果 [l + 1, r - 1] 表示的區(qū)間為空，不用判斷，也一定是回文串
// [l + 1, r - 1] 一定至少有 2 個元素 等價于 l + 1 < r - 1，即 r - l > 2
// 寫代碼的時候這樣寫：如果 [l + 1, r - 1] 的元素小于等于 1 個，即 r - l <= 2 ，就不用做判斷了
// 因為只有 1 個字符的情況在最開始做了判斷
// 左邊界一定要比右邊界小，因此右邊界從 1 開始
for (int r = 1; r < len; r++) {
for (int l = 0; l < r; l++) {
// 區(qū)間應該慢慢放大
// 狀態(tài)轉(zhuǎn)移方程：如果頭尾字符相等并且中間也是回文
// 在頭尾字符相等的前提下，如果收縮以后不構(gòu)成區(qū)間（最多只有 1 個元素），直接返回 True 即可
// 否則要繼續(xù)看收縮以后的區(qū)間的回文性
// 重點理解 or 的短路性質(zhì)在這里的作用
if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
dp[l][r] = true;
if (r - l + 1 > longestPalindrome) {
longestPalindrome = r - l + 1;
longestPalindromeStr = s.substring(l, r + 1);
}
}
}
}
return longestPalindromeStr;
}
}
寫完代碼以后，請讀者在紙上寫下代碼運行的流程，以字符串 'babad' 為例：
