題目描述
https://leetcode-cn.com/problems/longest-palindromic-substring/
給定一個字符串 s恰力，找到 s 中最長的回文子串扇丛。你可以假設(shè) s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"
思路分析
暴力解法
解決一個問題如果沒有思路飒焦，就要想辦法從簡單粗暴的解法開始，然后想辦法優(yōu)化它。
以"babad"為例灰瞻，
- 子串長度為1的時候，必然是回文
- 子串長度為2的時候辅甥，[ba,ab,ba,ad]酝润，需要兩個字符串相等才是回文
- 子串長度為3的時候，[bab,aba,bad]璃弄，需要從兩邊向中心依次判斷字符是否相等
- 子串長度為4的時候要销，[baba,abad]。判斷方式同3
- ...
因此得到了一個暴力的解法夏块，就是三層循環(huán)疏咐，
- 第一層循環(huán)是子串的長度規(guī)模(12345)
- 第二層循環(huán)是遍歷每個子串(ba ab ba ad)
- 第三層循環(huán)是對比首尾的字符是否相等
時間復雜度
空間復雜度
動態(tài)規(guī)劃
- 子串長度為1的時候，必然是回文
- 子串長度為2的時候脐供，[ba,ab,ba,ad]浑塞，需要兩個字符串相等才是回文
- 子串長度為3的時候，[bab,aba,bad]政己，需要從兩邊向中心依次判斷字符是否相等
- 子串長度為4的時候酌壕，[baba,abad]。判斷方式同3
- ...
基于暴力解法歇由，我們發(fā)現(xiàn)3是可以復用1的結(jié)論的卵牍，4是可以復用2的結(jié)論的，5是可以復用3的結(jié)論的沦泌，因此就發(fā)現(xiàn)了DP的一個要素（重疊子問題）
DP的其它要素是最優(yōu)子結(jié)構(gòu)糊昙、子問題獨立，以及狀態(tài)轉(zhuǎn)移方程
狀態(tài)轉(zhuǎn)移方程：
dp[i][j]表示子串長度為i時谢谦，從j開頭的子串是否為回文
s表示字符串
長度為1的時候必然是回文释牺，
長度為2的時候取決于前后兩個字符串是否相等
其它情況則3看1,4看2萝衩，這樣看之前的是否是回文，然后判斷子串的首尾兩個是否是回文
根據(jù)狀態(tài)轉(zhuǎn)移方程填寫dp數(shù)組船侧，最后得到問題結(jié)果
時間復雜度
空間復雜度
中心擴展法
然后再基于動態(tài)規(guī)劃解法的思路欠气，分析下能否進一步縮小空間復雜度
本題要求最大的回文子串，并不需要O(n^2)的空間來記錄下所有規(guī)模的子串是否為回文镜撩，
基于動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程以及直覺觀察预柒，可以發(fā)現(xiàn)要求最大回文子串有這樣一個規(guī)律
以babad為例，只需要從某一個中心開始袁梗，向左向右對比
以b為軸宜鸯，向左右擴展，只擴展到b自身
以b|a之間為軸遮怜，向左右擴展淋袖，可以擴展出ba
以a為軸，向左右擴展锯梁，可以擴展出即碗，a、aba
以此類推陌凳，這樣的時間復雜度還是
但是空間復雜度縮小到了
即只需要存儲每一輪的左右擴展后的子串
源碼
動態(tài)規(guī)劃
public class MyDpSolution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) {
return "";
}
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++) {
// i表示規(guī)格
for(int j = 0; j < s.length() - i; j++){
if(i == 0){
dp[i][j] = true;
} else if(i == 1) {
dp[i][j]= s.charAt(j) == s.charAt(j+1);
} else {
dp[i][j] = s.charAt(j) == s.charAt(j+i) && dp[i-2][j+1];
}
}
}
for(int i = s.length() - 1; i >= 0; i--) {
for(int j = 0; j + i < s.length(); j++) {
if(dp[i][j]) {
return s.substring(j, j + i + 1);
}
}
}
return "";
}
}
中心擴展法
public class MyCenterExternSolution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) {
return "";
}
if(s.length() == 1) {
return s;
}
int max_m = 0;
int max_n = 0;
int max = 0;
for(int i = 1; i < s.length() * 2; i++) {
int m,n,len=0;
if((i & 1) == 0) {
// i是偶數(shù)剥懒，說明中心點在一個字母上
m = i / 2;
n = i / 2;
} else {
// i是奇數(shù)，說明中心點在字母之間
m = (i - 1) / 2;
n = (i + 1) / 2;
}
while(m >= 0 && n < s.length() && s.charAt(m) == s.charAt(n)) {
m--;
n++;
len = n - m;
}
if(len > max) {
max = len;
max_m = m+1;
max_n = n-1;
}
}
return s.substring(max_m, max_n + 1);
}
}
