【LeetCode 5】最长回文串

港控/mmm° 2023-02-18 03:30 27阅读 0赞

#### 题目描述 ####

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

示例 1：

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

示例 2：

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

#### 解题思路 ####

使用中心扩展的方法：

*  选取对称中心（奇数长度的字符串为中心两个字符的中间，偶数长度的字符串中心为中间的字符）
 *  通过对比选择出两种组合较大的回文子串长度
 *  对比之前的长度，判断是否更新起始的位置
 *  遍历完之后，根据起始位置，截取最长回文子串

#### 代码实现 ####

/** * @param {string} s * @return {string} */
    var longestPalindrome = function(s) { 
        if(s == null || s.length <1){ 
            return ''
        }
        let start = 0
        let end = 0
        // 定义中心扩展的方法
        const fn = (s,left,right) => { 
            while(left >=0 && right< s.length && s[left] === s[right]){ 
                left--
                right++
            }
            return right - left -1
        }
        // 遍历字符串
        for(let i = 0; i<s.length; i++){ 
            const len1 = fn(s, i, i)
            const len2 = fn(s, i, i+1)
            const len = Math.max(len1, len2)
            // 判断起始位置是否更新
            if(len > end - start){ 
                start = i- Math.floor((len-1)/2)
                end = i+ Math.floor(len/2)
            }
        }
        return s.substring(start, end+1)
    };

#### 提交结果 ####

![在这里插入图片描述][20200616012427367.png]

[20200616012427367.png]: https://img-blog.csdnimg.cn/20200616012427367.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode5.最长回文子串

目录题目链接题目分析解题思路暴力中心向两边拓展搜索题目链接 [链接]

水深无声/ 2024年03月25日 23:37/ 0 赞/ 53 阅读

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

目录题目思路动态规划题目来源 [5. 最长回文子串][5.] 题目思路本题和[LeetCode-647. 回文子串][Le

﹏ヽ暗。殇╰゛Y/ 2024年03月24日 13:18/ 0 赞/ 70 阅读

相关最长回文子串(leetcode5)

求一个字符串的最长回文子串，我们可以将以每个字符为首的子串都遍历一遍，判断是否为回文，如果是回文，再判断最大长度的回文子串。算法简单，但是算法复杂度太高，O（n^3）

小咪咪/ 2023年06月03日 14:53/ 0 赞/ 30 阅读

相关【LeetCode 5】最长回文串

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

港控/mmm°/ 2023年02月18日 03:30/ 0 赞/ 28 阅读

相关 LeetCode-5 最长回文子串

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

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

相关 leetcode5最长回文子串

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

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

相关 Leetcode 5. 最长回文子串

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

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

相关【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。示例 1： > 输入: “babad” > 输出: “bab”

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

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

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

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