如何找到字符串中的最长回文子串?「建议收藏」

如何找到字符串中的最长回文子串?「建议收藏」作者|channingbreeze责编|胡巍巍小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。可是努…

大家好,又见面了,我是你们的朋友全栈君。

640?wx_fmt=gif

640?wx_fmt=jpeg

作者 | channingbreeze

责编 | 胡巍巍

640?wx_fmt=jpeg

小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。可是努力了很久,别说BAT了,连TMD的橄榄枝都没有接到。

640?wx_fmt=jpeg

可是他越挫越勇。这不,今天他又去一家互联网小巨头公司面试了。

640?wx_fmt=jpeg

640?wx_fmt=png

面试现场

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:只要先对比第一个字符和倒数第一个字符,再对比第二个字符和倒数第二个字符,以此类推。如果都相等,那就是回文串了。

640?wx_fmt=jpeg

题目:给你一个字符串,找出里面最长的回文子串。

例如,输入abcdcef,那么输出应该是cdc;

输入adaelele,输出应该是elele。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

半分钟过去了。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:可以遍历整个字符串,把每个字符和字符间的空隙当作回文的中心,然后向两边扩展来找到最长回文串。小史这次抢着分析时间和空间复杂度。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

一分钟过去了。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=png

请教大神

小史回到学校,把面试情况和吕老师说了一下。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

吕老师:比如cabadabae用中心扩展的算法,我已经知道了第三位为中心的aba和第5位为中心的abadaba是回文,那么在判断第7位为中心的回文串的时候,有什么已知信息吗?

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:已知第5位为中心的abadaba是回文,由回文的特性,就能够知道2-4位和6-8位对称,而又知道第3位为中心的aba是回文,所以2-4位是回文。这样的话,6-8位肯定是回文。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史拿着笔在纸上画了半天,突然大叫一声。

640?wx_fmt=jpeg

小史:由于之前的计算,已经知道了第5位为中心的abadaba是回文,而第4位为中心的a的回文长度是1,所以第6位为中心的回文长度只能是1,不用再去扩展判断了。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:以第7位为中心的回文串的计算,由之前分析已经知道最小长度是3了,但是还是需要进行扩展,因为第9位是什么,根据之前的信息无法得知,需要扩展进行探索。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:而以第6位为中心的回文串的计算,并不需要进行探索了,因为根据之前第5位为回文中心串的信息、和第4位为回文中心串的信息,已经可以推断,第6位为回文中心串的长度只能为1。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:当然可以。

1、首先,我们要记录下目前已知的回文串能够覆盖到的最右边的地方,就像案例中的第8位

2、同时,覆盖到最右边的回文串所对应的回文中心也要记录,就像案例中的第5位

3、以每一位为中心的回文串的长度也要记录,后面进行推断的时候能用到,就像案例中用到的以第3位为中心的回文和第4位为中心的回文

4、对于新的中心,我们判断它是否在右边界内,若在,就计算它相对右边界回文中心的对称位置,从而得到一些信息,同时,如果该中心需要进行扩展,则继续扩展就行。


640?wx_fmt=png

编码实现


640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:回文的中心有可能是两个字符中间,这种情况没有考虑到啊。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

小史:

1、先对字符串进行预处理,两个字符之间加上特殊符号#;

2、然后遍历整个字符串,用一个数组来记录以该字符为中心的回文长度,为了方便计算右边界,我在数组中记录长度的一半(向下取整);

3、每一次遍历的时候,如果该字符在已知回文串最右边界的覆盖下,那么就计算其相对最右边界回文串中心对称的位置,得出已知回文串的长度;

4、判断该长度和右边界,如果达到了右边界,那么需要进行中心扩展探索。当然,如果第3步该字符没有在最右边界的“羽翼”下,则直接进行中心扩展探索。进行中心扩展探索的时候,同时又更新右边界;

5、最后得到最长回文之后,去掉其中的特殊符号即可。

640?wx_fmt=jpeg

640?wx_fmt=jpeg

理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:

PlalindromeString.java:

 

/**
 * @author xiaoshi on 2018/9/24.
 * Happy Mid-Autumn Festival
 */

public class PlalindromeString {

    // 判断一个字符串是否回文,算法中用不到了
    @Deprecated
    private boolean isPlalindrome(String s) {

        int len = s.length();
        for(int i = 0; i < len / 2; i++) {

            if(s.charAt(i) != s.charAt(len – 1 – i)) {

                return false;
            }
        }
        return true;
    }

    // 预处理字符串,在两个字符之间加上#
    private String preHandleString(String s) {

        StringBuffer sb = new StringBuffer();
        int len = s.length();
        sb.append(‘#’);
        for(int i = 0; i < len; i++) {

            sb.append(s.charAt(i));
            sb.append(‘#’);
        }
        return sb.toString();
    }

    // 寻找最长回文字串
    public String findLongestPlalindromeString(String s) {

        // 先预处理字符串
        String str = preHandleString(s);
        // 处理后的字串长度
        int len = str.length();
        // 右边界
        int rightSide = 0;
        // 右边界对应的回文串中心
        int rightSideCenter = 0;
        // 保存以每个字符为中心的回文长度一半(向下取整)
        int[] halfLenArr = new int[len];
        // 记录回文中心
        int center = 0;
        // 记录最长回文长度
        int longestHalf = 0;
        for(int i = 0; i < len; i++) {

            // 是否需要中心扩展
            boolean needCalc = true;
            // 如果在右边界的覆盖之内
            if(rightSide > i) {

                // 计算相对rightSideCenter的对称位置
                int leftCenter = 2 * rightSideCenter – i;
                // 根据回文性质得到的结论
                halfLenArr[i] = halfLenArr[leftCenter];
                // 如果超过了右边界,进行调整
                if(i + halfLenArr[i] > rightSide) {

                    halfLenArr[i] = rightSide – i;
                }
                // 如果根据已知条件计算得出的最长回文小于右边界,则不需要扩展了
                if(i + halfLenArr[leftCenter] < rightSide) {

                    // 直接推出结论
                    needCalc = false;
                }
            }
            // 中心扩展
            if(needCalc) {

                while(i – 1 – halfLenArr[i] >= 0 && i + 1 + halfLenArr[i] < len) {

                    if(str.charAt(i + 1 + halfLenArr[i]) == str.charAt(i – 1 – halfLenArr[i])) {

                        halfLenArr[i]++;
                    } else {

                        break;
                    }
                }
                // 更新右边界及中心
                rightSide = i + halfLenArr[i];
                rightSideCenter = i;
                // 记录最长回文串
                if(halfLenArr[i] > longestHalf) {

                    center = i;
                    longestHalf = halfLenArr[i];
                }
            }
        }
        // 去掉之前添加的#
        StringBuffer sb = new StringBuffer();
        for(int i = center – longestHalf + 1; i <= center + longestHalf; i += 2) {

            sb.append(str.charAt(i));
        }
        return sb.toString();
    }

}

Main.java:

 

/**
 * @author lixin on 2018/9/24.
 */

public class Main {

    public static void main(String[] args{

        PlalindromeString ps = new PlalindromeString();

        String[] testStrArr = new String[] {

            “abcdcef”,
            “adaelele”,
            “cabadabae”,
            “aaaabcdefgfedcbaa”,
            “aaba”,
            “aaaaaaaaa”
        };

        for(String str : testStrArr) {

            System.out.println(String.format(“原字串 : %s”, str));
            System.out.println(String.format(“最长回文串 : %s”, ps.findLongestPlalindromeString(str)));
            System.out.println();
        }

    }

}

运行结果:

 

原字串 : abcdcef
最长回文串 : cdc

原字串 : adaelele
最长回文串 : elele

原字串 : cabadabae
最长回文串 : abadaba

原字串 : aaaabcdefgfedcbaa
最长回文串 : aabcdefgfedcbaa

原字串 : aaba
最长回文串 : aba

原字串 : aaaaaaaaa
最长回文串 : aaaaaaaaa

640?wx_fmt=jpeg

640?wx_fmt=png

时间空间分析

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

640?wx_fmt=jpeg

作者简介:channingbreeze,国内某互联网公司全栈开发。

声明:本文为作者投稿,版权归对方所有。作者独立观点,不代表 CSDN 立场。

苹果手机的微信改版了,

想快速看到CSDN的热乎文章,

赶快把CSDN公众号设为星标吧,

打开公众号,点击“设为星标”就可以啦!

640?wx_fmt=png

安卓手机的用户,

点击公众号右上角小人,就可以置顶啦。

640?wx_fmt=png



征稿啦

CSDN 公众号秉持着「与千万技术人共成长」理念,不仅以「极客头条」、「畅言」栏目在第一时间以技术人的独特视角描述技术人关心的行业焦点事件,更有「技术头条」专栏,深度解读行业内的热门技术与场景应用,让所有的开发者紧跟技术潮流,保持警醒的技术嗅觉,对行业趋势、技术有更为全面的认知。

如果你有优质的文章,或是行业热点事件、技术趋势的真知灼见,或是深度的应用实践、场景方案等的新见解,欢迎联系 CSDN 投稿,联系方式:微信(guorui_1118,请备注投稿+姓名+公司职位),邮箱(guorui@csdn.net)。

推荐阅读:

640?wx_fmt=gif

640?wx_fmt=gif

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130228.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Vmware安装win10的失败总结

    Vmware安装win10的失败总结下了番茄,萝卜,深度等多个win10镜像均出现各种莫名其妙的小问题,还是linux大法好哇~~失败一:          未手动分区,许久不装windows系统了,忘记了手动分区,用镜像里自带的分区工具,如diskgenius等分区后安装失败二:          分区后需进入bios设置优先从光盘启动的模式失败三:          找不到ghost文件,进入winPE手动查找光盘里…

  • java中jvm面试题_mysql基础面试题及答案

    java中jvm面试题_mysql基础面试题及答案Jvm面试题及答案(Jvm面试题大全带答案)发现网上很多Jvm面试题及答案整理都没有答案,所以花了很长时间搜集,本套Jvm面试题大全,有大量经典的Jvm面试题以及答案,包含Jvm语言常见面试题、面试经验技巧等,应届生,实习生,企业工作过的,都可参考学习!如果不背Jvm面试题的答案,肯定面试会挂!这套Jvm面试题大全,希望对大家有帮助哈~博主已将以下这些面试题整理成了一个面试手册,是PDF版的1、ZGC了解吗?JDK11中加入的具有实验性质的低延迟垃圾收集器,目标是尽可能在不影响吞吐

  • 错误的类文件:apache-tomcat-7.0.73-windows-x64\apache-tomcat-7.0.73 \lib\servlet-api.jar(javax/servlet/http

    错误的类文件:apache-tomcat-7.0.73-windows-x64\apache-tomcat-7.0.73 \lib\servlet-api.jar(javax/servlet/http错误的类文件:apache-tomcat-7.0.73-windows-x64\apache-tomcat-7.0.73 \lib\servlet-api.jar(javax/servlet/http

  • java months between,ORACLE函数MONTHS_BETWEEN

    java months between,ORACLE函数MONTHS_BETWEEN因系统折旧月份是按当月是否满15天来算是否为一个月,故此研究了下MONTHS_BETWEEN已适应折旧的逻辑官网函数说明:MONTHS_BETWEENreturnsnumberofmonthsbetweendatesdate1anddate2.Ifdate1islaterthandate2,thentheresultispositive.Ifdate1…

  • windows下git server搭建

    windows下git server搭建

  • Javascript:谈谈JS的全局变量跟局部变量

    Javascript:谈谈JS的全局变量跟局部变量今天公司一个实习小妹子问我两段JS代码的区别:vara=”Hello”;functiontest(){vara;alert(a);a=”World”;alert(a);}vara=”Hello”;functiontest(){alert(a);a=

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号