欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【字符串】最长回文子串

程序员文章站 2022-03-26 13:29:40
想要看更加舒服的排版、更加准时的推送关注公众号“不太灵光的程序员”每日八点有干货推送,微信随时解答你的疑问5 最长回文子串 python3中等 字符串给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1:输入: “babad”输出: “bab”注意: “aba” 也是一个有效答案。示例 2:输入: “cbbd”输出: “bb”分析过程回文串 就是 正序和逆序是一个结果的字符串叫回文串最长回文子串 是找出 在字符串中 正序和逆序是一....

想要看更加舒服的排版、更加准时的推送
关注公众号“不太灵光的程序员”
每日八点有干货推送,微信随时解答你的疑问

5 最长回文子串 python3

中等 字符串

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

示例 1:

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

示例 2:

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

分析过程
回文串 就是 正序和逆序是一个结果的字符串叫回文串
最长回文子串 是找出 在字符串中 正序和逆序是一个结果的子串

# 86%
# 执行用时:812 ms
# 内存消耗:13.7 MB
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2: return s

        max_len = 0
        start_index = 0

        def hw_len(left, right):
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1, left + 1

        # 中心扩散法
        for i in range(n-1):
            # 单核心
            len1, start_index1 = hw_len(i, i)
            # 双核心
            len2, start_index2 = hw_len(i, i+1)

            if len1 > max_len:
                max_len = len1
                start_index = start_index1
            if len2 > max_len:
                max_len = len2
                start_index = start_index2

        return s[start_index: start_index+max_len]


s = Solution()
st = "cbbd"
ret = s.longestPalindrome(st)
print(ret, 'bb')
st = "babad"
ret = s.longestPalindrome(st)
print(ret, 'bab')
st = "abcda"
ret = s.longestPalindrome(st)
print(ret, "a")
st = "ac"
ret = s.longestPalindrome(st)
print(ret, 'a')
st = "bb"
ret = s.longestPalindrome(st)
print(ret, 'bb')
st = ""
ret = s.longestPalindrome(st)
print(ret)
st = "aacedaa"
ret = s.longestPalindrome(st)
print(ret, "aa")
st = "aacdefcaa"
ret = s.longestPalindrome(st)
print(ret, "aa")
st = "saacdefcaa"
ret = s.longestPalindrome(st)
print(ret, "aa")
st = "abcdbbfcba"
ret = s.longestPalindrome(st)
print(ret, "bb")
st = "onoranynartionso"
ret = s.longestPalindrome(st)
print(ret, "ranynar")

【字符串】最长回文子串

本文地址:https://blog.csdn.net/qq_23934063/article/details/107477318