一、题目描述

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

示例 1：

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

示例 2：

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

提示：

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

二、分析调试过程

2.1、判断是否是回文

def is_huiwen(s):
    if s == s[::-1]:
        return True
    else:
        return False

2.2、获取字符串的所有子集

def get_sonstr(s):
    results = []
    # x + 1 表示子字符串长度
    for x in range(len(s)):
        # i 表示偏移量
        for i in range(len(s) - x):
            results.append(s[i:i + x + 1])
    return results

2.3、获取列表中最长的字符串

res = max(huiwen_list, key=len)

2.4、最终代码如下

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        huiwen_list = []


        def is_huiwen(s):
            if s == s[::-1]:
                return True
            else:
                return False


        def get_sonstr(s):
            results = []
            # x + 1 表示子字符串长度
            for x in range(len(s)):
                # i 表示偏移量
                for i in range(len(s) - x):
                    results.append(s[i:i + x + 1])
            return results


        for sonstr in get_sonstr(s):
            # print "回文列表为：%s" % huiwen_list
            if is_huiwen(sonstr):
                huiwen_list.append(sonstr)

        if huiwen_list:
            res = max(huiwen_list, key=len)
            return str(res)

结果超出时间限制，是因为使用了多个for 循环

2.5、查看题解后找到类似解决办法

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if s==s[::-1]:
            return s
        max_len = 1
        res = s[0]
        for i in range(len(s) - 1):
            for j in range(i + 1, len(s)):
                if j - i + 1 > max_len and s[i:j+1] == s[i:j+1][::-1]:
                    max_len = j - i + 1
                    res = s[i:j + 1]
        return res

解析如下：

1、判断字符串本身是否为回文
2、判断最长子集是否是回文
   最长子集由j - i + 1 > max_len决定，子集为s[i:j+1]

三、心得体会

子集办法使用多层循环导致复杂度大，运行超时；查阅题解,发现大多数使用动态规划和中心扩散法，需要接下来学习一下

四、参考文档

1、https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-jian-dan-de-bao-li-jie-ti-bi-dong-ta-2aki/

2、https://leetcode.cn/problems/longest-palindromic-substring/solution/pythonguan-jie-bao-li-fa-dong-tai-zhong-xin-kuo-sa/

3、https://blog.csdn.net/weixin_49859373/article/details/122323167

4、https://blog.csdn.net/jiangjiang_jian/article/details/79453856