这是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]

运行结果：

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