中心扩散算法——最长回文字符串

81 阅读 0 评论 54 点赞

我是靠谱客的博主眼睛大网络，最近开发中收集的这篇文章主要介绍中心扩散算法——最长回文字符串，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定一个字符串s，找到s中的最长回文字符串并返回这个最长的回文字符串

同时笔者在写这道题目的时候也在本地idea中碰到了一个问题，也写在了文章最后。

这里先把题目和笔者的解题思路向大家展现一下

示例：

解题思路：

定义下标变量，逐一比较，如果其一个字符的左边字符与其相同则长度变量len++，如果一个字符的右边字符与其相同则长度变量len++,如果其左右两边的字符都相同则len+2。循环这个过程，直到全部遍历完成。

循环比较部分代码（外部还有一个大的for循环，这里为了便于大家看懂，就只展示循环判断部分的代码）：

                 while (left>=0&&s.charAt(left)==s.charAt(i)){
                    len++;
                    left--;
                }
                while (right<strlen&&s.charAt(right)==s.charAt(i)){
                    len++;
                    right++;
                }
                while (left>=0&&right<strlen&&s.charAt(right)==s.charAt(left)){
                    len=len+2;
                    left--;
                    right++;
                }

left,right为定义的下标变量，strlen为字符串的总体长度，len为回文字符串的长度

判断是否为最长，定义了一个变量maxlen会记录第一次循环时，找到的回文字符串的长度，并且在每次循环之后都会将len的值重新变为1。后续继续循环比较，会比较maxlen与len的值，如果maxlen小于len,则用当前得len的值替换掉原maxlen的值。直到外围的大循环完全结束，然后通过substring方法来获取最长的回文字符串的值并将其最终返回。

完整代码：

public class demo2 {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        Solution2 a =new Solution2();
        a.longestPalindorme(s);
        System.out.println(a.longestPalindorme(s));
    }
}
class Solution2{
        public String longestPalindorme(String s) {
            if (s == null || s.length() == 0) {
                return "";
            }
            int strlen=s.length();
            int left=0;
            int right=0;
            int len=1;
            int maxStar=0;
            int maxLen=0;
            for (int i=0;i<strlen;i++){
                left=i-1;
                right=i+1;
                while (left>=0&&s.charAt(left)==s.charAt(i)){
                    len++;
                    left--;
                }
                while (right<strlen&&s.charAt(right)==s.charAt(i)){
                    len++;
                    right++;
                }
                while (left>=0&&right<strlen&&s.charAt(right)==s.charAt(left)){
                    len=len+2;
                    left--;
                    right++;
                }
                if (len>maxLen){
                    maxLen=len;
                    maxStar=len;
                }
                len=1;
            }
            return s.substring(maxStar+1,maxStar+maxLen+1);
        }

    }

这里遇到一个问题，在leetcode内置编译器时可以通过测试，并成功提交。但在本地idea中进行运行测试时，会产生超出下标问题。这个问题，笔者也觉得奇怪，也欢迎各位在评论区讨论。