最长回文子串——Python

发布于 2022-12-09  193 次阅读


这是leetcode上的第五题

题目描述

给你一个字符串s,找到s中最长的回文子串

示例1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例2:

输入:s = "cbbd"
输出:"bb

提示

  • 1 <= s.length <= 1000
  • s仅由数字和英文字母组成

尝试解题

要找出最长的回文子串,最容易想到的就是穷举,列出所有的可能性,然后逐个判断,取最长的子串。因为是子串,而不是子序列,穷举也具有可行性,但是效率肯定很低。
这里我尝试从最大的长度(即字符串的长度)开始列举,长度逐次减一,一旦符合条件,便直接return,这样不用去比较长度,第一个符合条件的肯定是最长的,得到的代码是这样的:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        ls = list(s)
        for i in range(length, 1, -1):
            for j in range(length - i + 1):
                if ls[j:j + i] == list(reversed(ls[j:j + i])):
                    return ''.join(ls[j:j + i])
        return s[0]

提交代码,果不其然,运行超时
超时
而我在自己的电脑上跑出来是这样的:
结果
可以看到,结果是很短的一串字符,而我是从最长的开始列举,这也算是遇上了比较坏的一种情况,Python本来运行效率就低,采取类似穷举的办法,很容易让程序跑半天。

改良代码

那该怎么办呢,难道要重写代码?呃,对我我这样一个懒人肯定是不愿意这样做的,那就直接在原代码上改。
经过分析,运行时间显然主要花在了对是否回文的判断,也就是list和reversed函数,如何减少这俩函数执行的次数,就是改良的关键。
其实这里方法很简单,直接在这层代码外面再加一层判断:看子串的首尾字符是否相同,如果相同则执行函数进行判断,不相同直接刷掉。
改过后的代码:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        ls = list(s)
        for i in range(length, 1, -1):
            for j in range(length - i + 1):
                if ls[j] == ls[j + i - 1]:
                    if ls[j:j + i] == list(reversed(ls[j:j + i])):
                        return ''.join(ls[j:j + i])
        return s[0]

运行结果:
通过

可以看到问题解决了,呃,可以写作业去了