栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

python 最长回文字符串 --力扣5 --中等

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

python 最长回文字符串 --力扣5 --中等

一、题目描述

给你一个字符串 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

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/893447.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号