Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >5. 最长回文子串

5. 最长回文子串

作者头像
张伦聪zhangluncong
发布于 2022-10-26 10:19:23
发布于 2022-10-26 10:19:23
91400
代码可运行
举报
运行总次数:0
代码可运行

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

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: "cbbd"
输出: "bb"

解:这题很经典,我们使用Manacher算法(中文名:马拉车算法)来解决。

1.回文分为奇回文(aa)和偶回文(aba),在代码中解决起来比较麻烦所以我们可以进行填充#使得所有回文变成奇数,如#a#a#和#a#b#a#,为了代码处理方便不越界,我们再在前面填充最终变成#a#a#和

2.这里我们设s_new[i]为我们的填充后新字符串,如下图;再引入一个辅助数组p[i]表示对应i索引字符为中心的最长回文子串半径。

  • 如p[1]表示s_new[1]也就是#为中心对应最长回文子串半径为1,就是最长回文子串为#,半径为1即#
  • p[2]表示s_new[2]也就是a为中心对应最长回文子串半径为2,就是最长回文子串为#a#,半径为#a
  • p[5]表示s_new[5]也就是#为中心对应最长回文子串半径为5,就是最长回文子串#a#b#b#a#,半径为#a#b#

3.设当前已知的最长回文子串中心为id,mx为最长右边界,i是我们要求的值p[i]的中心,我们可以求得i关于id的对称点j=2*id-i,如下图。当mx>i的时候有p[i]=Math.min(p[2 * id - i], mx - i),具体解释看代码里面注释;但mx<=i的时候我们直接设p[i]=1,然后不断探索最长回文子串的左右边界,然后更新mx和id的值。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        // 预处理字符串,避免奇偶问题
        String str = preProcess(s);
        int id = 0;
        //mx 代表以 id 为中心的最长回文的右边界
        int mx = 0;
        //用来保存最长回文子串的中心
        int maxId = 0;
        //用来保存最长回文子串的半径
        int maxSpan = 0;
        //辅助数组p[i]代表对应字符串str中下标为i为中心的最长子串的半径
        int[] p = new int[str.length()];
        //跳过$符从#开始
        for (int i = 1; i < str.length(); i++) {
            //可能很多人不明白2 * id - i表示的是以id为中心最长子串i对应的另一个对标点,也就是
            //上图的j;如上图因为i,j是关于id的对称点,并且还是当前以id为中心最长子串的子集,所以
            //p[2 * id - i]的值也就是p[i]的值,但是因为mx > i,所以mx-i也是一个以i为中心的子串半径
            //i子串半径不能大于mx-i所以用一个min函数比较。
            p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 1;
            //探索当前p[i]半径的边界
            while ((i + p[i]) < str.length() && str.charAt(i + p[i]) == str.charAt(i - p[i])) {
                p[i]++;
            }
            //如果右边界值大于mx,那要更新mx的值和id值
            if (i + p[i] > mx) {
                mx = p[i] + i;
                id = i;
            }
            //保存最新的最长子串半径和中点
            if (p[i] > maxSpan) {
                maxSpan = p[i];
                maxId = i;
            }
        }
        //去除占位符所以要除以2
        return s.substring((maxId - maxSpan) / 2, (maxSpan + maxId) / 2 - 1);
    }

    private String preProcess(String s) {
        // 如ABC,变为$#A#B#C#
        StringBuilder sb = new StringBuilder();
        sb.append("$");
        for (int i = 0; i < s.length(); i++) {
            sb.append("#");
            sb.append(s.charAt(i));
        }
        sb.append("#");
        return sb.toString();
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-08-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
最长回文子串——马拉车算法详解
马拉车算法(Manacher‘s Algorithm)是用来解决求取一个字符串的最长回文子串问题的。此算法充分利用了回文字符串的性质,将算法复杂度降到了线性,非常值得一学。
全栈程序员站长
2022/07/01
8860
最长回文子串——马拉车算法详解
笔试面试算法经典–最长回文子串
正读和反读都相同的字符序列为“回文”,如“abba”、“abccba”是“回文”,“abcde”和“ababab”则不是“回文”。字符串的最长回文子串,是指一个字符串中包含的最长的回文子串。例如“1212134”的最长回文子串是“12121”。下面给出了三种求最长子串的方法。
全栈程序员站长
2022/06/28
4190
笔试面试算法经典–最长回文子串
最长回文子串——马拉车算法
针对最长回文子串相关的问题,马拉车算法应该是比较通用的解法,今天我们就来具体看看这个算法。
健程之道
2020/03/11
8110
LeetCode - 最长回文子串
同样是三年前做的一道题目,很经典的字符串领域的算法题,求字符串的最长回文子串,当时我也是提交了好几次,并且看了相关的资料以后,才成功通过。
晓痴
2019/07/24
6950
LeetCode - 最长回文子串
字符串--最长回文子串(暴力讲解+Manacher)
问题描述:给你一个字符串str,若子串s是回文串,则称s为str的回文子串,求s的最大长度
用户2965768
2018/08/30
1.2K0
字符串--最长回文子串(暴力讲解+Manacher)
BAT面试算法进阶(5)- 最长回文子串(方法一)
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
iOSSir
2023/03/19
2520
BAT面试算法进阶(5)- 最长回文子串(方法一)
最长回文子串&最长子串&第K大的数字&atoi
其实,我们知道,对于回文子串来说,是对称的。也就是说,从中心开始,往左扩散,往右扩散,一直去比较左右两边,如果一样,就再去往左扩散,往后扩散,直到结束,如果出现不相等的情况,那就说明不是回文子串。我们来举个例子:
平凡的人1
2022/11/15
3070
最长回文子串&最长子串&第K大的数字&atoi
Day14-字符串-最长回文子串
后台有小伙伴私信说,希望增加一些栏目。这些建议我都会认真听取,等我闲下来的时候,一定把公众号功能丰富一些,比如自动回复,增加别的栏目什么的~
BUPTrenyi
2019/07/15
5140
Day14-字符串-最长回文子串
算法修炼之筑基篇——筑基二层初期(解决最长回文子串问题,马拉车(manacher)算法模板)
通过填充动态规划表格 dp,可以找到最长回文子串的长度和起始位置。该方法的时间复杂度为 O(n^2)。
命运之光
2024/03/20
2790
算法修炼之筑基篇——筑基二层初期(解决最长回文子串问题,马拉车(manacher)算法模板)
寻找最长回文子串
字符串“PATZJUJZTACCBCC”的最长回文子串为“ATZJUJZTA”,长度为9。
全栈程序员站长
2022/08/31
4270
如何求最长回文子串
回文字符串,就是像“12321”这种轴对称形式的字符串。 但并不是所有的字符串都是这种整个串都是回文串的,比如1232。有些计算机问题就是在一个字符串中找出一段最长的回文字符子串,这个时候时候,我们就需要一些算法来求出结构。
全栈程序员站长
2022/08/24
3740
如何求最长回文子串
LeetCode【5】-- 最长回文子串(马拉车算法)
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-palindromic-substring,著作权归领扣网络所有。
秦怀杂货店
2022/02/15
3020
LeetCode【5】-- 最长回文子串(马拉车算法)
四种方法求最长回文子串
所谓回文串,就是正着读和倒着读结果都一样的回文字符串。 比如: a, aba, abccba都是回文串, ab, abb, abca都不是回文串。
全栈程序员站长
2022/09/06
1K0
四种方法求最长回文子串
【算法沉淀】最长回文子串
题目解析: 给定一个字符串s,需要找到s中最长的回文子串。回文字符串是指正序和反序都相同的字符串。
苏泽
2024/03/10
990
【算法沉淀】最长回文子串
最长回文子串
给你一个字符串 s,找到 s 中最长的回文子串。啥是回文串?就是字符可以看成是对称的,从左往右读和从右往左读是一样意思,比如:上海自来水来自海上。来看下下面的示例:
用户4456933
2021/06/01
7140
Go算法实战 - 5.【最长回文子串LeetCode-5】
原题链接 https://leetcode-cn.com/problems/longest-palindromic-substring/
junedayday
2021/08/05
3450
#1032 : 最长回文子串
小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。
全栈程序员站长
2022/09/07
5060
计算最长回文子串_用递归判断是否为回文字符串
前面我们讲过一个关于字符串的算法:KMP算法。今天我们来讲另外一个字符串算法:Manacher算法。这个算法是用于解决一个问题叫:最长回文子串。
全栈程序员站长
2022/11/19
6500
计算最长回文子串_用递归判断是否为回文字符串
LeetCode刷题DAY 2:最长回文子串
之前刷过回文相关的题(LeetCode刷题DAY 1:回文数判断),本次再来一道跟回文相关的问题——找到最长回文子串。该题目是LeetCode热门100题之一,也是动态规划的经典问题之一,对逻辑能力还是有一定考验。
三猫
2020/05/09
3590
[c/c++]——最长回文子串「建议收藏」
已经很久没有更新关于leetcode的题解了,一个是觉得太费时间,二一个目前网上也有很全面的解答,但是在写leetcode的最长回文子串时,发现很多同学的代码都很长(实际上几行就可以解决的事情),并且c++解答的代码不够完整。最关键的是在一种“马拉车”的算法卡了很久很久,今天把几种求解的方法全部都整理出来,方便大家也便于自己以后复习。
全栈程序员站长
2022/08/15
4160
[c/c++]——最长回文子串「建议收藏」
推荐阅读
相关推荐
最长回文子串——马拉车算法详解
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验