題目描述
給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"
暴力
根據回文子串的定義，枚舉所有長度大于等于 2 的子串，依次判斷它們是否是回文；
在具體實作時，可以隻針對大于“目前得到的最長回文子串長度”的子串進行“回文驗證”；
在記錄最長回文子串的時候，可以隻記錄“目前子串的起始位置”和“子串長度”，不必做截取。這一步我們放在後面的方法中實作。
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// s.charAt(i) 每次都會檢查數組下标越界，是以先轉換成字元數組，小細節
char[] charArray = s.toCharArray();
// 枚舉所有長度大于 1 的子串 charArray[i..j]
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
//j - i + 1 > maxLen這個用的很精髓。利用&&運算的短路特征，寫在前面會優化許多。
if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
/**
* 驗證子串 s[left..right] 是否為回文串
*/
private boolean validPalindromic(char[] charArray, int left, int right) {
while (left < right) {
if (charArray[left] != charArray[right]) {
return false;
}
left++;
right--;
}
return true;
}
}
動态規劃
第 1 步：定義狀态
dp[i][j] 表示子串 s[i…j] 是否為回文子串，這裡子串 s[i…j] 定義為左閉右閉區間，可以取到 s[i] 和 s[j]。
第二步，列出狀态轉移方程。
依然從回文串的定義展開讨論：
如果一個字元串的頭尾兩個字元都不相等，那麼這個字元串一定不是回文串；
如果一個字元串的頭尾兩個字元相等，才有必要繼續判斷下去。
如果裡面的子串是回文，整體就是回文串；
如果裡面的子串不是回文串，整體就不是回文串。
dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]
「動态規劃」事實上是在填一張二維表格，由于構成子串，是以 i 和 j 的關系是 i <= j ，是以，隻需要填這張表格對角線以上的部分。
求 長度為 1 和長度為 2 的 dp(i,j) 時不能用上邊的公式，因為我們代入公式後會遇到 dp[i][j] 中 i > j 的情況，比如求 P[1][2] 的話，我們需要知道 dp[1+1][2-1]=dp[2][1] ，而 dp[2][1] 代表着 S[2,1] 是不是回文串，顯然是不對的，是以我們需要單獨判斷。
public class Solution {
public String longestPalindrome(String s) {
// 特判
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i, j] 是否是回文串
boolean[][] dp = new boolean[len][len];
char[] charArray = s.toCharArray();
//初始化。
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {
//下面if else可以用 || 運算來代替，增加可讀性。因為 || 有短路功能。
//dp[i][j] = charArray[i] == charArray[j] && (j - i < 3 || dp[i + 1][j - 1]);
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else if (j - i < 3) {
//長度為3,中間不用考慮，而且相等，那麼就是true。
dp[i][j] = true;
} else{
dp[i][j] = dp[i + 1][j - 1];
}
// 隻要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此時記錄回文長度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
下面分别展示了錯誤的填表順序和正确的填表順序，以便大家了解動态規劃要滿足「無後效性」的意思。
說明：表格中的數字表示「填表順序」，從 1 開始。表格外的箭頭和數字也表示「填表順序」，與表格中的數字含義一緻。
方法三：中心擴散法
暴力法采用雙指針兩邊夾，驗證是否是回文子串。
除了枚舉字元串的左右邊界以外，比較容易想到的是枚舉可能出現的回文子串的“中心位置”，從“中心位置”嘗試盡可能擴散出去，得到一個回文串。
是以中心擴散法的思路是：周遊每一個索引，以這個索引為中心，利用“回文串”中心對稱的特點，往兩邊擴散，看最多能擴散多遠。
枚舉“中心位置”時間複雜度為 O(N)，從“中心位置”擴散得到“回文子串”的時間複雜度為 O(N)，是以時間複雜度可以降到 O(N^2)。
在這裡要注意一個細節：回文串在長度為奇數和偶數的時候，“回文中心”的形式是不一樣的。
奇數回文串的“中心”是一個具體的字元，例如：回文串 “aba” 的中心是字元 “b”；
偶數回文串的“中心”是位于中間的兩個字元的“空隙”，例如：回文串串 “abba” 的中心是兩個 “b” 中間的那個“空隙”。
我們看一下一個字元串可能的回文子串的中心在哪裡？
我們可以設計一個方法，相容以上兩種情況：
1、如果傳入重合的索引編碼，進行中心擴散，此時得到的回文子串的長度是奇數；
2、如果傳入相鄰的索引編碼，進行中心擴散，此時得到的回文子串的長度是偶數。
具體編碼細節在以下的代碼的注釋中展現。
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
String res = s.substring(0, 1);
// 中心位置枚舉到 len - 2 即可，區間是[0,len -2]
for (int i = 0; i < len - 1; i++) {
String oddStr = centerSpread(s, i, i);
String evenStr = centerSpread(s, i, i + 1);
String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
if (maxLenStr.length() > maxLen) {
maxLen = maxLenStr.length();
res = maxLenStr;
}
}
return res;
}
private String centerSpread(String s, int left, int right) {
// left = right 的時候，此時回文中心是一個字元，回文串的長度是奇數
// right = left + 1 的時候，此時回文中心是一個空隙，回文串的長度是偶數
int len = s.length();
int i = left;
int j = right;
while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
// 這裡要小心，跳出 while 循環時，恰好滿足 s.charAt(i) != s.charAt(j)，是以不能取 i，不能取 j
return s.substring(i + 1, j);
}
}
馬拉車算法，自行參考下面兩篇文章
https://www.jianshu.com/p/392172762e55
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/