LeetCode_05_最长回文子串
1.题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
2.思路分析与代码实现
其实看到这个题，我最先联想到的是滑动窗口法，但仔细想想好像不太一样。
方法一：动态规划
我看到了动态规划算法：
① 思考状态
状态先尝试“题目问什么，就把什么设置为状态”。然后考虑“状态如何转移”，如果“状态转移方程”不容易得到，尝试修改定义，目的仍然是为了方便得到“状态转移方程”。
② 状态转移方程
技巧是分类讨论。对状态空间进行分类，思考最优子结构到底是什么。即大问题的最优解如何由小问题的最优解得到。
动态规划的本质就是打表格，从一个小规模问题出发，逐步得到大问题的解，并记录过程。动态规划依然是“空间换时间”思想的体现。
③ 思考初始化
初始化是非常重要的，一步错，步步错，初始化状态一定要设置对，才可能得到正确的结果。
角度 1：直接从状态的语义出发；
角度 2：如果状态的语义不好思考，就考虑“状态转移方程”的边界需要什么样初始化的条件；
角度 3：从“状态转移方程”方程的下标看是否需要多设置一行、一列表示“哨兵”，这样可以避免一些边界的讨论，使得代码变得比较短。
④ 思考输出
有些时候是最后一个状态，有些时候可能会综合所有计算过的状态。
⑤ 思考状态压缩
“状态压缩”会使得代码难于理解，初学的时候可以不一步到位。先把代码写正确，然后再思考状态压缩。
状态压缩在有一种情况下是很有必要的，那就是状态空间非常庞大的时候（处理海量数据），此时空间不够用，就必须状态压缩
第 1 步：定义状态
dp[i][j] 表示子串 s[i, j] 是否为回文子串。
第 2 步：思考状态转移方程
根据头尾字符是否相等做分类讨论，根据上面的分析得到：
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
分析这个状态转移方程：
（1）“动态规划”事实上是在填一张二维表格，i 和 j 的关系是 i <= j ，因此，只需要填这张表的上半部分；
（2）看到 dp[i + 1][j - 1] 就得考虑边界情况。
边界条件是：表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2，即 j - 1 - (i + 1) + 1 < 2 ，整理得 j - i < 3。
这个结论很显然：当子串 s[i, j] 的长度等于 2 或者等于 3 的时候，我其实只需要判断一下头尾两个字符是否相等就可以直接下结论
3.代码
package part1;
/**
* @author haiboWu
* @create 2020-01-30 19:20
*/
public class No_05 {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(longestPalindrome("babad"));
}
public static String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
boolean dp[][] = new boolean[s.length()][s.length()];
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
int maxLen = 1;
int start = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (s.charAt(i) == s.charAt(j)) {
if (i - j < 3) {
dp[j][i] = true;
} else {
dp[j][i] = dp[j + 1][i - 1];
}
} else {
dp[j][i] = false;
}
if (dp[j][i]) {
int len = i - j + 1;
if (len > maxLen) {
maxLen = len;
start = j;
}
}
}
}
return s.substring(start, start+maxLen);
}
}
方法二：中心扩散法
遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。
在这里要注意一个细节：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。
- 奇数回文串的“中心”是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b"；
偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串 "abba" 的中心是两个 "b" 中间的那个“空隙”。
所有的间隙
package part1;
/**
* @author haiboWu
* @create 2020-01-30 19:28
*/
public class No_05_2 {
public static void main(String[] args) {
System.out.println(longestPalindrome("ababd"));
}
public static String longestPalindrome(String s){
int n = s.length();
if (n < 2) {
return s;
}
int maxLen=1;
String res=s.substring(0,1);
for(int i=0;i<n-1;i++){
String s1=getMaxString(s,i,i);
String s2=getMaxString(s,i,i+1);
String maxLenStr=s1.length()>s2.length()?s1:s2;
if(maxLenStr.length()>maxLen){
maxLen=maxLenStr.length();
res=maxLenStr;
}
}
return res;
}
public static String getMaxString(String s,int left,int right){
int n=s.length();
while(left>=0&&right<n){
if(s.charAt(left)==s.charAt(right)){
left--;
right++;
}else{
break;
}
}
return s.substring(left+1,right);
}
}
3.参考
上面两种时间复杂度都为O(N),还有第三种时间复杂度为O(N)的方法：Manacher算法
