题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
来源：力扣（LeetCode）
代码实现
class Solution {
public String longestPalindrome(String s) {
int i = 1;
String res;
int count0 = 0;
int count = 0;
int j = 0,j0 = 0;
while(i < s.length()){
int h = 1;
int h0 = 1;
while(i - h >= 0 && i + h < s.length()){
if(s.charAt(i - h) == s.charAt(i +h)){
h++;
}
else{
break;
}
}
while(i - h0 >= 0 && i + h0 - 1 < s.length()){
if(s.charAt(i - h0) == s.charAt(i + h0 - 1)){
h0++;
}
else{
break;
}
}
h0--;
h--;
if(count0 < h0){
j0 = i;
count0 = h0;
}
if(count < h){
j = i;
count = h;
}
i++;
}
if(count >= count0){
res = s.substring(j - count,j +count +1);
}
else{
res = s.substring(j0 - count0,j0 + count0);
}
return res;
}
}思路整理
这个题目我还是挺自豪的，第一时间就想到了正确的思路，虽然不知道运用了什么原理。
首先第一念头必定是暴力手段，列举出所有子串。但是明显不合适。
我想的是，回文以中间为对称轴，两边的字符必定是对称相等的。
所以先遍历字符串，使每一个字符作为回文子串的中心字符，然后给定一个h，判断以索引处为中心，s.charAt(i - h）和s.charAt(i + h)是否相同，如果相同就h++，继续左移和右移判断是否相同，这样就可以判断以索引为i处的字符为中心的最长回文子串。先给定一个j和count，用来记录最大回文子串处的i和h。这样最后截取s.substring(j - count,j +count +1)作为即可。
要注意的是，因为s.charAt(i - h）和s.charAt(i + h)相同后要h++继续判断下两个字符，所以到最后h是多加了一个1，所以循环判定完后i--即可。
尝试一把，发现{b,b}不对，是我忽略了回文子串长度为偶数的情况，也不用着急，使用类似的思路加一层判定即可，原本是i -?h 和i +?h处字符判断是否相等，现在是i - h 和i +h -1处字符是否相等，即回文字符中心是i - 1 和i + 1 - 1（即i）。原本的h,j,count设成h0,j0,count0即可。
最后加一层逻辑判断，由于count == count0时截取的字符偶数字符串要少一个字符，所以必须count0 > count才使用偶数的count0,j0进行截取。
最后我怕也去看了官方题解，这里采用的是动态规划思想，把回文子串的对称字符一层层去掉，他仍是回文串，所以去到最后变成了一个字符或者空串。
?