给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:
输入: “cbbd”
输出: “bb”
思路
遍历字符串,对于某个子串,如果其左右两边的字符依然相等,就继续遍历,得到最长的长度,最后
截取子串即可
思路不难,最重要的是判定清楚边界条件,下面的代码就有三个地方要弄清楚,这也是我将这个题记录下来的原因
class Solution {
public String longestPalindrome(String s) {
if(s.length()==0)return "";
int start=0;
int end=0;
char[] ch=s.toCharArray();
for(int i=0;i<ch.length;i++){
//两种回文,一是一个中心,二是两个中心
int len1=huiwen(ch,i,i);
int len2=huiwen(ch,i,i+1);
int len=Math.max(len1,len2);
if(len>end-start){
//因为对于huiwen(ch,i,i+1)
//长度是从i开始左右计算的,所以i左边的数比右边的少一个
//在往左寻开始坐标的时候先减一
start=i-(len-1)/2;
end=i+len/2;
}
}
//end是闭区间的右边,substring 中终点是不纳入的
return s.substring(start,end+1);
}
public int huiwen(char[] s,int l,int r){
if(l>r)return 0;
while((l>=0&&r<s.length)&&s[l]==s[r]){
l--;
r++;
}
//返回区间长度然后由于左右都加了1所以减掉2,得到回文长度
return (r-l+1)-2;
}
}