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

最长回文子串

程序员文章站 2022-05-29 07:52:01
...

其实最简单的就是暴力法,但是python3会超时(也不知道出题人搞那么多a干啥)
学习了中心扩展的方法,易懂,但我觉得不太容易操作(对于我这个菜鸟来说),当然,得知palindrome用法时就大概懂了,原来大部分代码时在限制条件,而回文确是一步到位。
最长回文子串

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size < 2:
            return s

        max_len = 1
        res = s[0]

        for i in range(size):
            palindrome_os, os_len = self.zhongxin(s, size, i, i)
            palindrome_js, js_len = self.zhongxin(s, size, i, i + 1)


            cur_max_sub = palindrome_os if os_len >= js_len else palindrome_js
            if len(cur_max_sub) > max_len:
                max_len = len(cur_max_sub)
                res = cur_max_sub
        return res

    def zhongxin(self, s, size, left, right):#构造函数
        i = left
        j = right
        while i >= 0 and j < size and s[i] == s[j]:
            j += 1
            i -= 1
        return s[i + 1:j], j - i - 1

最长回文子串

相关标签: 打卡