hot100-5最长回文子串
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例一
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
代码
1. 暴力解法
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++) {
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;
}
}2. 动态规划
从一个最基本的问题出发，逐步计算中间过程，最后得到要求问题的解。
第 1 步：定义状态
dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j]。
第 2 步：思考状态转移方程
在这一步分类讨论（根据头尾字符是否相等），根据上面的分析得到：
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
说明：
- 「动态规划」事实上是在填一张二维表格，由于构成子串，因此 i 和 j 的关系是 i <= j ，因此，只需要填这张表格对角线以上的部分。
- 看到 dp[i + 1][j - 1] 就得考虑边界情况。
边界条件是：表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 1，即 j - 1 - (i + 1) + 1 < 1 ，整理得 j - i < 2。
这个结论很显然：j - i < 2 等价于 j - i + 1 < 3，即当子串 s[i..j] 的长度等于 2 的时候，其实只需要判断一下头尾两个字符是否相等就可以直接下结论了。
- 如果子串 s[i + 1..j - 1] 只有 1 个字符，即去掉两头，剩下中间部分只有 1 个字符，显然是回文；
- 如果子串 s[i + 1..j - 1] 为空串，那么子串 s[i, j] 一定是回文子串。
因此，在 s[i] == s[j] 成立和 j - i < 2 的前提下，直接可以下结论，dp[i][j] = true，否则才执行状态转移。
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if(len<2)return s;
int maxLen = 1;
int begin = 0;
boolean [][] dp = new boolean[len][len];
char[] charArray = s.toCharArray();
for(int j=0;j<len;j++){
for(int i=0;i<=j;i++){
if(charArray[i]!=charArray[j]){
dp[i][j] = false;
}else{
if(j-i<2){
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);
}
}3. 中心扩散
暴力法采用双指针两边夹，验证是否是回文子串。
除了枚举字符串的左右边界以外，比较容易想到的是枚举可能出现的回文子串的“中心位置”，从“中心位置”尝试尽可能扩散出去，得到一个回文串。
因此中心扩散法的思路是：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。
枚举“中心位置”时间复杂度为 O(N)，从“中心位置”扩散得到“回文子串”的时间复杂度为 O(N)，因此时间复杂度可以降到 O(N^2)。
在这里要注意一个细节：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。
奇数回文串的“中心”是一个具体的字符，例如：回文串 “aba” 的中心是字符 “b”；
偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串 “abba” 的中心是两个 “b” 中间的那个“空隙”。
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 即可
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) {
if (s.charAt(i) == s.charAt(j)) {
i--;
j++;
} else {
break;
}
}
// 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
return s.substring(i + 1, j);
}
}
