温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

leetcode 5:最长回文子串

发布时间:2020-07-09 07:15:32 来源:网络 阅读:266 作者:Jayce_SYSU 栏目:编程语言

题目描述

Given a string s, find the longest palindromic substring in s.
You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"
# -*- coding: utf-8 -*-
# @Time         : 2019-10-11 10:34
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : longestPalindromicSubstring.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    """
    要查找最长的回文子串,这里可以把我们的思路换一下。
    原本我们判断一个字符串是不是回文的时候,是从字符串的两端开始往中间比较,
    而我们现在要找的是最长的回文子串,那么如果我们从中间开始往两段比较,直到待比较的两个字符不相等。

    通过不断的将中心字符移动,这样我们就可以找到最长的回文子串。
    需要注意的是,在我们判断一个字符串的是不是回文的时候需要处理字符串个数的奇偶性
    同理,我们在移动中心字符的时候,也要处理奇数字符长度的回文子串和偶数字符长度的回文子串。
    """
    def longestPalindrome(self, s):
        def helper(left, right):
            """
            判断给定一个字符串的起止点,最多能将其延长到多长。
            :param left: 起点
            :param right: 终点
            :return: 以left, right为起止点能延长到的最长回文字符串
            """
            # 只要下标不越界并且两端相等,就往外延伸
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # 当不能再延伸的时候,返回当前能得到的最长回文字符串
            return s[left + 1: right]

        ans = ''
        for i in range(len(s)):
            # 对于每一个中心,需要判断奇数长度的回文子串和偶数长度的回文子串
            odd = helper(i, i)
            if len(odd) > len(ans):
                ans = odd
            even = helper(i, i + 1)
            if len(even) > len(ans):
                ans = even
        return ans

def main():
    solution = Solution()
    s = "babad"
    print(solution.longestPalindrome(s))

if __name__ == '__main__':
    main()
向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI