Leetcode5--最长回文子串(双指针中心扩散法)

题目

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

 解析

题目要求是找到正着念和反着念都相同的字串,那么有两种解决方式。

  • 从两边到中间聚集
  • 从中间到两边扩散

如果从两边到中间聚集,我们是没有办法确定,两边的边界在哪里,互相对应的边界是什么的。而从中间到两边扩散的话,只需要遍历各个节点,然后依次向两边扩散遍历即可,所以这道题的思路可以选择从中间到两边扩散。

当我们遇到左右边界对应的节点不相等的时候,结束当前节点作为中心节点即可。然后更新res(结果)的值。每个位置向两边扩散都会出现一个窗口大小(len)。如果 len>maxLen(用来表示最长回文串的长度)。则更新 maxLen 的值。并且因为最后要返回的是字串,而不是长度,所以最后还需要记录left,right的位置,截取字符串,然后返回。

代码

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for(int i = 0;i< s.length();i++){
            //奇数形式,以一个字符为中心
            String s1 = palindrome(s,i,i);
             //偶数形式,以两个字符为中心
            String s2 = palindrome(s,i,i+1);
            res = res.length() > s1.length()?res:s1;
            res = res.length() > s2.length()?res:s2;
        }
        return res;
    }
    String palindrome(String s,int left,int right){
        //防止越界,并且向两边扩散的条件s.charAt(left)==s.charAt(right)
        while(left >= 0&&right<s.length()
        &&s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
          // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substring(left+1,right);
    }

}

上一篇:Taro + vue3 实现自定义返回栏


下一篇:pg内核之日志管理器(五)WAL日志-WAL主要流程