5. 最长回文子串

╰半夏微凉° 2022-12-21 09:27 331阅读 0赞

# 1、题目描述 #

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

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

示例 2：

> 输入: “cbbd”  
> 输出: “bb”

# 2、求解 #

class Solution:
        def longestPalindrome(self, s: str) -> str:
            s_len = len(s)
            if s_len < 2:
                return s
            start_index = 0
            end_index = 0
            max_len = 0
            index = 0
            while index < s_len:
                left = index
                right = index
                # 找到当前所查找的回文串的中间位置
                # 需要首先跳过重复的字符
                while right < s_len - 1 and s[right] == s[right+1]:
                    right += 1
                # index用于记录下次开始查询回文串的可能中间位置
                index = right + 1
    
                # 分别从left和right向左右两边查找，判断最长的回文串
                while left > 0 and right < s_len - 1 and s[left-1] == s[right+1]:
                    left -= 1
                    right += 1
                
                # 判断当前找到的回文串是否更长
                curr_len = right - left + 1
                if curr_len > max_len:
                    start_index = left
                    end_index = right+1
                    max_len = curr_len
                
            return s[start_index:end_index]

发表评论取消回复

表情：

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

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

相关阅读

相关 5最长回文子串

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

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

相关 5. 最长回文子串

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

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

相关 5. 最长回文子串

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

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

相关 5. 最长回文子串

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

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

相关 5. 最长回文子串

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

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

相关 Leetcode 5. 最长回文子串

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

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

相关 5. 最长回文子串

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

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

相关 5. 最长回文子串

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

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

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

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

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

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

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

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