1. 题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = "babad"
输出："bab"
2. 两种解题思路
2.1 动态规划
思路：对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。
我们用一个 boolean dp[l][r] 表示字符串从 i 到 j 这段是否为回文。
试想如果 dp[l][r]=true，我们要判断 dp[l-1][r+1] 是否为回文。只需要判断字符串在(l-1)和（r+1)两个位置是否为相同的字符
动态规划关键是找到初始状态和状态转移方程。
-
初始状态，l=r 时，此时 dp[l][r]=true。
-
状态转移方程，dp[l][r]=true 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=true。
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];
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < len; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= len) {
break;
}
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
2.2 中心扩散法
思路：从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束
每个位置向两边扩散都会出现一个窗口大小（len）。如果 len>maxLen(用来表示最长回文串的长度）。则更新 maxLen 的值。
public String longestPalindrome(String s) { // 中心扩散
if (s == null || s.length() == 0) {
return "";
}
int strLength = s.length();
int left = 0;
int right = 0;
int len = 1; //当前回文串长度
int maxStar = 0; //回文串起始值
int maxLen = 0; //回文串最大长度
for (int i = 0; i < strLength; i++) {
left = i - 1;
right = i + 1;
//左边与当前值相等
while (left >= 0 && s.charAt(left) == s.charAt(i)) {
len++;
left--;
}
//右边与当前值相等
while (right < strLength && s.charAt(right) == s.charAt(i)) {
len++;
right++;
}
//左右相等
while (left >= 0 && right < strLength && s.charAt(right) == s.charAt(left)) {
len = len + 2;
left--;
right++;
}
//更新最长回文串长度，起始值
if (len > maxLen) {
maxLen = len;
maxStar = left;
}
len = 1;
}
return s.substring(maxStar + 1, maxStar + maxLen + 1);
}