题目描述
https://leetcode-cn.com/problems/longest-palindromic-substring/
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
思路分析
暴力解法
解决一个问题如果没有思路，就要想办法从简单粗暴的解法开始，然后想办法优化它。
以"babad"为例，
- 子串长度为1的时候，必然是回文
- 子串长度为2的时候，[ba,ab,ba,ad]，需要两个字符串相等才是回文
- 子串长度为3的时候，[bab,aba,bad]，需要从两边向中心依次判断字符是否相等
- 子串长度为4的时候，[baba,abad]。判断方式同3
- ...
因此得到了一个暴力的解法，就是三层循环，
- 第一层循环是子串的长度规模(12345)
- 第二层循环是遍历每个子串(ba ab ba ad)
- 第三层循环是对比首尾的字符是否相等
时间复杂度
空间复杂度
动态规划
- 子串长度为1的时候，必然是回文
- 子串长度为2的时候，[ba,ab,ba,ad]，需要两个字符串相等才是回文
- 子串长度为3的时候，[bab,aba,bad]，需要从两边向中心依次判断字符是否相等
- 子串长度为4的时候，[baba,abad]。判断方式同3
- ...
基于暴力解法，我们发现3是可以复用1的结论的，4是可以复用2的结论的，5是可以复用3的结论的，因此就发现了DP的一个要素（重叠子问题）
DP的其它要素是最优子结构、子问题独立，以及状态转移方程
状态转移方程：
dp[i][j]表示子串长度为i时，从j开头的子串是否为回文
s表示字符串
长度为1的时候必然是回文，
长度为2的时候取决于前后两个字符串是否相等
其它情况则3看1,4看2，这样看之前的是否是回文，然后判断子串的首尾两个是否是回文
根据状态转移方程填写dp数组，最后得到问题结果
时间复杂度
空间复杂度
中心扩展法
然后再基于动态规划解法的思路，分析下能否进一步缩小空间复杂度
本题要求最大的回文子串，并不需要O(n^2)的空间来记录下所有规模的子串是否为回文，
基于动态规划的状态转移方程以及直觉观察，可以发现要求最大回文子串有这样一个规律
以babad为例，只需要从某一个中心开始，向左向右对比
以b为轴，向左右扩展，只扩展到b自身
以b|a之间为轴，向左右扩展，可以扩展出ba
以a为轴，向左右扩展，可以扩展出，a、aba
以此类推，这样的时间复杂度还是
但是空间复杂度缩小到了
即只需要存储每一轮的左右扩展后的子串
源码
动态规划
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表示规格
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是偶数，说明中心点在一个字母上
m = i / 2;
n = i / 2;
} else {
// i是奇数，说明中心点在字母之间
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);
}
}
