提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

5. 最长回文子串

2023-04-18 16:11:22 时间

核心思路：

1.看到这题目很容易想到回文序列其实就是中心对称字符串，我们只要从中心开始找找到两边字符串不同的位置即停止即可，这样按个去遍历

本结题思路有几点特别巧妙，写完之后感觉挺爽 2.本题目把相同的一段元素看成一个元素比较这段元素两边的字符即可

3.每次跳过最后一个相同的元素取不同的元素，这样减少了很多计算量，这也使得这个代码超越了不少解法

idea leetcode插件

代码：

class Solution {
    public String longestPalindrome(String s) {
        //用于存放最大长度区间值
        int[] range=new int[2];
        char[] chars = s.toCharArray();
        for (int i = 0,len=chars.length; i <len; i++) {
            // 把回文看成中间的部分全是同一字符，左右部分相对称
            // 找到下一个与当前字符不同的字符，这样可以减少不少重复计算
            i=findLongest(chars,i,range);
        }
        return s.substring(range[0],range[1]+1);
    }

    private int findLongest(char[] chars, int low, int[] range) {
        //初始位置为当前字符位置，找到重复元素的最后一个元素位置
        int high=low;
        while (high+1<chars.length&&chars[high+1]==chars[low]){
            high++;
        }

        //找到重复元素两边对称位置不相同的元素位置
        //保存最后一个和low位置元素的重复元素位置
        int ans=high;
        while (low>0&&high<chars.length-1&&chars[low-1]==chars[high+1]){
            low--;
            high++;
        }

        if (high-low>range[1]-range[0]){
            range[1]=high;
            range[0]=low;
        }
        return ans;
    }
}

相关文章