python实现对求解最长回文子串的动态规划算法
作者:bailang_zhizun 发布时间:2023-11-09 10:18:49
基于Python实现对求解最长回文子串的动态规划算法,具体内容如下
1、题目
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
2、求解
对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解。
关于动态规划的含义及用法,请参考链接,这篇文章通过漫画的形式对动态规划算法进行了详细而又有风趣的介绍。值得一看。
2.1 算法一
利用常规动态规划算法,即利用表来存储每一中回文子串的可能。
基于动态规划的三要素对问题进行分析,可确定以下的状态转换方程:
其中f(i,j)表示当s[i:j]子串是否是回文串。当j-i<=1时,如果s[i] == s[j]则表示s[i:j]为回文串,及f(i,j) = true,否则f(i,j) = false。当j-i > 1时,则判断 s[i]、s[j]是否相等以及f(i+1, j-1)是否为true,即s[i+1:j-1]是否为回文串,如果为真,则f(i,j) = true
所以就需要一个n*n的二维矩阵用于存储f(i,j)的值,其中 j in range(0, k),i in range(0, j+1),之所以是j+1是因为i可以等于j。
python3代码如下:
k = len(s) # 计算字符串的长度
matrix = [[0 for i in range(k)] for i in range(k)] # 初始化n*n的列表
logestSubStr = "" # 存储最长回文子串
logestLen = 0 # 最长回文子串的长度
for j in range(0, k):
for i in range(0, j+1):
if j - i <= 1:
if s[i] == s[j]:
matrix[i][j] = 1 # 此时f(i,j)置为true
if logestLen < j - i + 1: # 将s[i:j]的长度与当前的回文子串的最长长度相比
logestSubStr = s[i:j+1] # 取当前的最长回文子串
logestLen = j - i + 1 # 当前最长回文子串的长度
else:
if s[i] == s[j] and matrix[i+1][j-1]: # 判断
matrix[i][j] = 1
if logestLen < j - i + 1:
logestSubStr = s[i:j+1]
logestLen = j - i + 1
return logestSubStr
采用当前算法,时间复杂度为O(n*n),空间复杂度为O(n*n),算法平均耗时大概5~7s
下面介绍空间复杂度为O(n)的算法。
2.2 算法二
算法二是由算法一改良而来,观察算法一的执行流程如下:
当j>1时,判断f(i,j)是否为回文子串的操作只与j-1时的的操作相关,即f(i,j) = g(f(i, j-1)),其中j>1,i in range(0, j+1),所以接下来就变成求解g()函数了。
用nlist存储j情况下所有的子串是否为回文子串的标志
用olist存储j-1情况下所有的子串是否为回文子串的标志
那么olist与nlist的关系是什么呢?
有上图可知,nlist[i] = g(olist[i+1])
新的算法如下:
k = len(s)
olist = [0] * k # 申请长度为n的列表,并初始化
nList = [0] * k # 同上
logestSubStr = ""
logestLen = 0
for j in range(0, k):
for i in range(0, j + 1):
if j - i <= 1:
if s[i] == s[j]:
nList[i] = 1 # 当 j 时,第 i 个子串为回文子串
len_t = j - i + 1
if logestLen < len_t: # 判断长度
logestSubStr = s[i:j + 1]
logestLen = len_t
else:
if s[i] == s[j] and olist[i+1]: # 当j-i>1时,判断s[i]是否等于s[j],并判断当j-1时,第i+1个子串是否为回文子串
nList[i] = 1 # 当 j 时,第 i 个子串为回文子串
len_t = j - i + 1
if logestLen < len_t:
logestSubStr = s[i:j + 1]
logestLen = len_t
olist = nList # 覆盖旧的列表
nList = [0] * k # 新的列表清空
return logestSubStr
这样新算法的空间复杂度就为O(2n),即O(n)。算法平均耗时3s左右,而且该算法更符合动态规划的原理。
来源:https://blog.csdn.net/bailang_zhizun/article/details/80538774
猜你喜欢
- 废话不多说了,直接给大家贴代码了。编写setup.py后$ python setup.py register$ python setup.p
- 由于是通过枚举字典的方式来实现的,因此在开始之前我们需要先构建好密码字典。通过对密码字典挨个进行试错的方式获取正确wifi名称和密码,此内容
- 在python处理数据时,经常用到DataFrame和set。train=pd.read_csv('XXX.csv')#读取
- 上一篇内容,已经学会了使用简单的语句对网页进行抓取。接下来,详细看下urlopen的两个重要参数url和data,学习如何发送数据data一
- 为了把事情变成简单化,我在多个Oracle数据上建立统一的检查数据库账户,并且账户只能访问特定的几个视图(需要查询的sql已生成视图),具体
- 说明字符串驻留是一种仅保存一份相同且不可变字符串的方法。不同的值被存放在字符串驻留池中,发生驻留之后, 许多变量可能指向内存中的相同字符串对
- Python中的闭包前几天又有人留言,关于其中一个闭包和re.sub的使用不太清楚。我在脚本之家搜索了下,发现没有写过闭包相关的东西,所以决
- 在一行内声明CSS,对比下面两个:h2 {font-size:18px; border:1px solid&n
- 一、概述OLAP的系统(即Online Aanalyse Process)一般用于系统决策使用。通常和数据仓库、数据分析、数据挖掘等概念联系
- 在炼丹时,数据的读取与预处理是关键一步。不同的模型所需要的数据以及预处理方式各不相同,如果每个轮子都我们自己写的话,是很浪费时间和精力的。P
- 姓名的翻译: 英语是名(First name)在前,姓(Last name)在后。中文地址的翻译:如果你英语水平不高,填表时只要国家名用英语
- PDO::getAttributePDO::getAttribute — 取回一个数据库连接的属性(PHP 5 >= 5.1.0, P
- Apache2 httpd.conf 中文版 # # 基于 NCSA 服务的配
- python 封装tokenimport datetimeclass MyJwt:def __init__(self): &n
- 使用re, urllib, threading多线程抓取天涯帖子内容,设置url为需抓取的天涯帖子的第一页,设置file_name为下载后的
- 创建与打开站点启动FrontPage XP,选择菜单“文件/新建”,再单击“网页或站点”命令选项。在“新建网页或站点”任务窗格
- 首先看一下来自Wolfram的定义 马尔可夫链是随机变量{X_t}的集合(t贯穿0,1,..
- 导语三月疫情原因,很多地方都封闭式管理了!在回家无聊的打酱油,小编今天给大伙带来了一波小游戏——全民
- 有关 Web 字体的话题正在增多,对 Web 设计师来说,他们并不关注技术细节,不管是 TrueType 的 Hinting 技术
- 如下所示:# -*- coding:utf8 -*-import osimport shutilimport numpy as npimpo