这是leetcode上的第五题

  题目描述

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

  示例1：

   输入：s = "babad"

    输出："bab"

  示例2：

   输入：s = "cbbd"

  提示

  尝试解题

  要找出最长的回文子串，最容易想到的就是穷举，列出所有的可能性，然后逐个判断，取最长的子串。因为是子串，而不是子序列，穷举也具有可行性，但是效率肯定很低。

  这里我尝试从最大的长度（即字符串的长度）开始列举，长度逐次减一，一旦符合条件，便直接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])

  提交代码，果不其然，运行超时

  而我在自己的电脑上跑出来是这样的：

  可以看到，结果是很短的一串字符，而我是从最长的开始列举，这也算是遇上了比较坏的一种情况，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])

  运行结果：

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