1.题目描述
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
2.思路
外层 i 表示回文子串的右端点
内层 j 表示回文子串的左端点
输入：s = “abccba”
补充
我们来判断 s[1…4] = “bccb” 是不是回文
j = 1, i = 4
s[1] = ‘b’, s[4] = ‘b’ → 相等 ✅
那么只要 s[2…3] = “cc” 是不是回文 → dp[2] = true
在前一轮 i=3 的时候，已经计算过 dp[2] = true（因为 “cc” 是回文）
→ 所以 dp[1] = dp[2] = true，说明 “bccb” 是回文 ✅
3.代码实现
class Solution {
public String longestPalindrome(String s) {
//初始化起始索引
int start=0;
int end=0;
boolean[] dp=new boolean[s.length()];
// 枚举右端 i
for(int i=0;i<s.length();i++)
{
// 枚举左端 j (0…i)
for(int j=0;j<=i;j++)
{
if(i==j)
{
dp[j]=true;//比如单个字符a就是回文子串，子串长度为1
}else if(j+1==i)//比如单个字符aa就是回文子串，子串长度为2
{
if(s.charAt(j)==s.charAt(i))
{
dp[j]=true;
}
else
{
dp[j]=false;
}
}else//aba情况， // 子串长度 ≥ 3
{
//那么中间的子串 s[j+1 … i-1] 是不是回文？
if(s.charAt(j)==s.charAt(i))
{
//对于 s[j…i] 来说，只要两端相等并且中间部分 s[j+1…i-1] 是回文，那么整个就是回文
//此时你已经算出上一轮 dp[j+1] 的结果，也就是 s[j+1…i-1] 是否是回文（注意右边 i 是当前轮固定的）；
//如果两端字符相等 s[j] == s[i] 且中间部分 s[j+1…i-1] 是回文（即 dp[j+1] == true），那么 s[j…i] 也是回文。
dp[j]=dp[j+1];
}
else
{
dp[j]= false;
}
}
if(dp[j]==true&&i-j>end-start)
{
//是判断当前子串 s[j…i] 是否是最长的回文子串，如果是，就更新记录的起止下标
end=i;
start=j;
}
}
}
// s.substring(start, end) 是左闭右开区间。
return s.substring( start,end+1);
}
}