Python3最长回文子串算法示例
作者:gxnustc 发布时间:2023-05-27 14:17:10
标签:Python,回文,算法
本文实例讲述了Python3最长回文子串算法。分享给大家供大家参考,具体如下:
1. 暴力法
思路:对每一个子串判断是否回文
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) == 1:
return s
re = s[0]
for i in range(0,len(s)-1):
for j in range(i+1,len(s)):
sta = i
end = j
flag = True
while sta < end:
if s[sta] != s[end]:
flag = False
break
sta += 1
end -= 1
if flag and j-i+1 > len(re):
re = s[i:j+1]
return re
提交结果:超出时间限制
2. 动态规划法
思路:
m[i][j]标记从第i个字符到第j个字符构成的子串是否回文,若回文值为True,否则为False.
初始状态 s[i][i] == True,其余值为False.
当 s[i] == s[j] and m[i+1][j-1] == True 时,m[i][j] = True
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
k = len(s)
matrix = [[False for i in range(k)] for j in range(k)]
re = s[0:1]
for i in range(k):
for j in range(k):
if i==j:
matrix[i][j] = True
for t in range(1,len(s)): #分别考虑长度为2~len-1的子串(长串依赖短串的二维数组值)
for i in range(k):
j = i+t
if j >= k:
break
if i+1 <= j-1 and matrix[i+1][j-1]==True and s[i] == s[j]:
matrix[i][j] = True
if t+1 > len(re):
re = s[i:j+1]
elif i+1 == j and j-1 == i and s[i] == s[j]:
matrix[i][j] = True
if t+1 > len(re):
re = s[i:j+1]
return re
执行用时:8612 ms
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/aawsdasd/article/details/80484938
0
投稿
猜你喜欢
- 如何修改程序默认时区由于系统安装时时区可能选择不对,并不是中国的东八区,导致依赖于日期时间函数无法正常使用找到一个比较简单的方法程序启动时加
- 目录开始安装使用一、安装 Python二、安装 moviepy三、安装 ffmpeg四、开始写拼接脚本五、等待运行完毕, 完结撒花 🎉六、补
- photoshop快捷键大全: 工具箱(多种工具共用一个快捷键的可同时按【Shift】加此快捷键选取)相关文章:网页设计软件FrontPag
- 本文主要给大家讲解了Apriori算法的基础知识以及Apriori算法python中的实现过程,以下是所有内容:1. Apriori算法简介
- 本文实例讲述了Python微信推送模板消息功能。分享给大家供大家参考,具体如下:官方文档:https://mp.weixin.qq.com/
- 方法1:/** 功能:数据备份/恢复文件简易方法* 以日期为单位,一天一个备份文件,以当天最后备份为准* 用提交表单的形式进行操作,* 其中
- 不通过数据源名DSN也能访问Access数据库吗?代码如下:<% dim conn &nbs
- 来介绍一下 Python 是采用何种途径解决循环引用问题的。上图中,表示的是对象之间的引用关系,从自对象指向他对象的引用用黑色箭头表示。每个
- 当获取FileField数据时会出现编码问题在数据库里显示的是D:\python项目\wxmkczpy\uploadfile\QQ截图201
- 针对很普遍的每个元素的操作会遍历每个元素进行操作。这里给出了几种写法,列表每个元素自增等数学操作同理;示例:整形列表ilist加1个数、元素
- pycharm部署anaconda环境Pycharm: python编辑器,社区版本Anaconda:开源的python发行版本(专注于数据
- 本文实例讲述了django框架实现一次性上传多个文件功能。分享给大家供大家参考,具体如下:在用django 写文件上传的时候,从reques
- 在 Pandas 中有很多种方法可以进行dataframe(数据框)的合并。本文将研究这些不同的方法,以及如何将它们执行速度的对比。合并DF
- 很久没有更新blog了,这段时间实在是发生了很多的事,累身累心。但还是有很多想做的事,比如更新merceCSS、把一直以来所总结的有关模块化
- 我们可以调用matplotlib 绘制我们的柱状图,柱状图可以是水平的也可以是竖直的。在这里我先记录下竖直的柱状图怎么绘制在这里一般用到的函
- 在编写python函数时,无意中发现一个问题:python中的变量不能以数字打头,以下函数中定义了一个变量3_num_varchar,执行时
- 以XML格式查看查询结果通过使用传统—xml 选项调用MySQL命令行客户程序,你可以以XML格式(而不是传统的列表形式
- 一般情况下TextArea区输入的文字数量是没有限制的,但是我们可以通过javascript限制表单的文字字数。如下javascript代码
- 内容摘要:有很多朋友虽然安装好了mysql但却不知如何使用它。在这篇文章中我们就从连接mysql、修改密码、增加用户等方面来学习一些mysq
- 最近刚开始学python,正好实习工作中遇到对excel中的数据进行处理的问题,就想到利用python来解决,也恰好练手。实际的问题是要从e