leetcode5-最长回文子串

原题

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例2:

输入: "cbbd"
输出: "bb"

解法

思想

以每个字符或两个字符中间的位置为中心向两边延申看能达到两边对称的最大长度,如果超过记录的最大长度就把start和end位置记录下来,最后根据start和end返回对应的子字符串。

代码

class Solution {
    int start = 0;
    int end = 0;
    char[] chars;
    public String longestPalindrome(String s) {
        if(s.equals("")) return "";
        chars = s.toCharArray();
        for(int i = 0;i<chars.length-1;i++){
            expandLength(i,i);
            expandLength(i,i+1);
        }
        return s.substring(start,end+1);
    }

    public void expandLength(int left,int right){
        if(chars[left] != chars[right]) return;
        while(left!=0&&right!=chars.length-1&&chars[left-1] == chars[right+1]){
            left--;
            right++;
        }
        if(right-left>end-start){
            start = left;
            end = right;
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode5-%e6%9c%80%e9%95%bf%e5%9b%9e%e6%96%87%e5%ad%90%e4%b8%b2/