LeetCode：最长回文子串

快来打我* 2021-11-22 15:20 316阅读 0赞

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

示例 1：

输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
    输出: "bb"

//O(n^2)解法，勉强AC
    class Solution {
    public:
        string longestPalindrome(string s) {
            int max_len = 0;
            int index,start, end;
            string res = "";
            if( s.length() == 0)
                return res;
            for(int i = 0; i < s.length(); i ++)
            {
                int len1 = expandString(s, i, i); // 情况a
                int len2 = expandString(s, i, i+1); //情况aa
                int len = max(len1, len2);
                if(len > max_len)
                    max_len = len, index = i;
            }
            if( max_len % 2 != 0 )
                start = index - (max_len-1)/2, end = index + (max_len-1)/2;
            else
                start = index - (max_len-2)/2, end = index + (max_len-2)/2 + 1;
            for(int i = start; i <= end; i ++)
                 res += s[i];
            return res;
        }
        int expandString(string s, int i, int j)
        {
            while(i >=0 && j < s.length() && s[i] == s[j])
            {
                i --;
                j ++;
            }
            return j- i - 1;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-5 最长回文子串

[LeetCode5][] 做法主要有三种：暴力搜索中心扩散法马拉车Manacher 暴力搜索和中心扩散法O(n^2) Manacher是O

﹏ヽ暗。殇╰゛Y/ 2022年12月08日 14:16/ 0 赞/ 136 阅读

相关最长回文子串

最长回文子串 1、参考资料 https://leetcode-cn.com/problems/longest-palindromic-substring/ htt

╰半夏微凉°/ 2022年12月08日 05:24/ 0 赞/ 170 阅读

相关 leetcode5最长回文子串

![在这里插入图片描述][20210602112131449.png] 思路：（1）使用dp\[i\]\[j\]来进行s\[i\]~s\[j\]子串是否为回文子串的标

布满荆棘的人生/ 2022年10月17日 10:40/ 0 赞/ 143 阅读

相关 Leetcode 5. 最长回文子串

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

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

相关最长回文子串

include <iostream> include <vector> include <string> include <algori

淩亂°似流年/ 2022年06月17日 06:53/ 0 赞/ 234 阅读

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

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

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

相关 LeetCode-5.最长回文子串

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

本是古典何须时尚/ 2022年01月31日 00:29/ 0 赞/ 228 阅读

相关 LeetCode最长回文子串——C

来源：力扣（LeetCode）链接：[https://leetcode-cn.com/problems/longest-palindromic-substring][ht

灰太狼/ 2022年01月07日 23:09/ 0 赞/ 174 阅读

相关 LeetCode：最长回文子串

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

快来打我*/ 2021年11月22日 15:20/ 0 赞/ 317 阅读

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

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

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