5. 最长回文子串

Bertha 。 2022-08-31 00:48 231阅读 0赞

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

示例 1：

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

输入：s = "cbbd"  
输出："bb"  
示例 3：

输入：s = "a"  
输出："a"  
示例 4：

输入：s = "ac"  
输出："a"

提示：

1 <= s.length <= 1000  
s 仅由数字和英文字母（大写和/或小写）组成

class Solution {
    public:
        string longestPalindrome(string s) {
            char ss[2000+5];
            ss[0]='$';
            int n = 1;
            for(int i = 0;i<s.size();i++)
            {
                ss[n++] = '#';
                ss[n++] = s[i];
            }
            ss[n++] = '#';
            ss[n++] = '^';
            ss[n] = 0;
            int p[2000+5]={0};
            int mx = 0;
            int id = 1;
            int mxlen = 0;
            int pos = 0;//记录最长的位置
            for(int i = 1;i<n;i++)
            {
                if(i<mx)
                p[i]=min(p[2*id-i],mx-i);
                else p[i]=1;
                while(ss[p[i]+i]==ss[i-p[i]]) p[i]++;
                if(mx<p[i]+i)
                {
                    mx = p[i]+i;
                    id = i;
                }
                if(p[i]-1>mxlen)
                {
                    pos = i-p[i];
                    mxlen = p[i]-1;
                }
            }
            return s.substr(pos/2,mxlen);
        }
    
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，231人围观）

还没有评论，来说两句吧...

相关阅读

相关 5最长回文子串

一、前言标签：动态规划、中心扩散。问题来源LeetCode 5 难度：中等。问题链接：[https://leetcode-cn.com/problems/lon

喜欢ヅ旅行/ 2023年02月28日 15:24/ 0 赞/ 21 阅读

相关 5. 最长回文子串

[5. 最长回文子串][5.] 1、参考资料 [LeetCode 官方题解][LeetCode] 2、题目要求 > 题目描述给定一个字符串 `s`，找到

傷城~/ 2022年12月29日 09:39/ 0 赞/ 208 阅读

相关 5. 最长回文子串

1、题目描述给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1： > 输入: “babad” > 输出: “b

╰半夏微凉°/ 2022年12月21日 09:27/ 0 赞/ 232 阅读

相关 5. 最长回文子串

> 给你一个字符串 s，找到 s 中最长的回文子串。 > > > > 示例 1： > > 输入：s = "babad" > 输出："bab" > 解释："ab

小鱼儿/ 2022年10月16日 10:00/ 0 赞/ 226 阅读

相关 5. 最长回文子串

[https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/][https_leet

川长思鸟来/ 2022年09月08日 03:58/ 0 赞/ 214 阅读

相关 Leetcode 5. 最长回文子串

题目重述给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的

灰太狼/ 2022年09月01日 00:59/ 0 赞/ 263 阅读

相关 5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2

Bertha 。/ 2022年08月31日 00:48/ 0 赞/ 232 阅读

相关 5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。示例 1：输入: "babad" 输出: "bab" 注意

红太狼/ 2022年05月20日 04:10/ 0 赞/ 246 阅读

相关【LeetCode】5. 最长回文子串

题目链接：[https://leetcode-cn.com/problems/longest-palindromic-substring/description/][https

比眉伴天荒/ 2022年05月03日 00:28/ 0 赞/ 263 阅读

相关 LeetCode（5）：最长回文子串

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。 ![20190809152320317.png][] 解法 1: 暴

淩亂°似流年/ 2021年11月06日 00:44/ 0 赞/ 429 阅读