河南省住房和城乡建设厅官方网站,制作一个网站并上传访问,网上购物商城建设,上海seo网站优化_搜索引擎排名_优化型企业网站建设_锦鱼网络要解决的问题#xff1a;
给定一个字符串#xff0c;要求求出这个字符串中的最长的回文串子串。
例子#xff1a;
cbddba的最长回文子串为 bddb
cbdedba的最长回文子串为dbedb
由上面的例子可以看到#xff0c;在考虑回文子串的问题时需要考虑奇偶性。因为奇回文关于中…要解决的问题
给定一个字符串要求求出这个字符串中的最长的回文串子串。
例子
cbddba的最长回文子串为 bddb
cbdedba的最长回文子串为dbedb
由上面的例子可以看到在考虑回文子串的问题时需要考虑奇偶性。因为奇回文关于中心的某个字符对称而偶回文关于最中心的两个元素之间的间隙对称。 一、动态规划法
在动态规划的思想中总是希望把问题划分成相关联的子问题然后从最基本的子问题出发来推导较大的子问题直到所有的子问题都解决。
首先要看一个较大的子问题与一个较小的子问题之间的关系
首先建立如下的函数 那么就能有如下的递推关系
当p(i1,j-1) true 的时候如果有si sj,那么 p(i,j)true也就是 abba中的bb为回文串那么在bb左边是a在bb右边也是a相同所以有abba也是回文串。
形式化表示如下 p(i,j) p(i1,j-1) and sisj 这就建立了较大问题与较小问题之间的关系。
然后考虑基本情况一个最基本的回文串有两种情况奇偶性
1 最基本的奇回文只有一个字符而且恒成立形式化表示为 p(i,i) true
2最基本的偶回文有两个字符当且仅当两个字符相等的时候成立p(i,j) (sisj and ji1)
最后获得如下判断一个字符是否为回文串的分段函数 有了公式就是用代码实现了下面给出了我的python实现。 # -*- coding:utf-8 -*-
# Author: Evan Mi# 测试的字符串
str_exp babad
# 用来保存动态规划过程的表 1表示true 0表示false
longest_palindromes [[-1] * len(str_exp) for i in range(len(str_exp))]
# longest_len 用来保存最长的回文串的长度
longest_len 1
# 从长度为1的回文子串开始填表
for p_len in range(1, len(str_exp)1):for i in range(len(str_exp)):j p_len i - 1if j len(str_exp):if i j:longest_palindromes[i][j] 1elif j i 1 and str_exp[i] str_exp[j]:longest_palindromes[i][j] 1longest_len p_lenelif j i1 and longest_palindromes[i1][j-1] 1 and str_exp[i] str_exp[j]:longest_palindromes[i][j] 1longest_len p_lenelse:longest_palindromes[i][j] 0
# 搜索结果表打印出所有的最优解
for i in range(len(str_exp)):for j in range(len(str_exp)):if longest_palindromes[i][j] 1 and j-i1 longest_len:print(str_exp[i:j1])
在动态规划中最最最核心的就是填表了就以程序中的例子babad举例说明一下填表的过程
首先我们要填的表是如下的一张表二维表因为p函数中有ij两个变量其中绿色的部分是真实的表格其他的是我家的解释表头。 填表过程如下首先填长度为1的; 然后填长度为2的 接着是长度为3的 长度为4的 最后是长度为5的 填表完成之后求最优解就是查询了对于时间复杂度动态规划的时间复杂度在构建表的过程中的基本操作所以时间复杂度是O(n^2);空间复杂度就是上面的二维数组也是O(n^2)。而且从在空间浪费主对角线下面的空间没有使用浪费了一般的空间。有很多针对空间上的优化方法下面给出一种空间复杂度为O(1)的算法 二、空间复杂度为O(1)的算法 该算法的主要思想就遍历所有的字符下标为i是以第i个数对应奇回文或者第i个数和第i1个数之间的间隙对应偶回文为中心向两边扩展直到扩展以后不再是回文那么就停止扩展如果回文长度比已知的最长回文长那么记录下该回问的开始位置和结束位置为最长回文
还是用babad来作为例子过程如下 代码实现如下 # -*- coding:utf-8 -*-
# Author: Evan Mi
import mathdef expandAroundCenter(left, right, s):从left和right之间开始扩展如果leftright就是以left/right为中心进行扩展rLeft leftrRight rightwhile rLeft 0 and rRight len(s) and s[rLeft] s[rRight]: # 进行扩展rLeft - 1rRight 1针对于返回的长度因为在while循环停止的时候rLeft和rRight都已经在要求的回文串之外了所以回文串的长度为rRight - rLeft - 1自己可以画个过程图一目了然。return rRight - rLeft - 1s babad
start 0
end 0for i in range(len(s)):odd_len expandAroundCenter(i, i, s) # i为中心的扩展even_len expandAroundCenter(i, i 1, s) # i 和 i1之间的空隙为中心进行扩展lens max(odd_len, even_len) # 取得本次扩展的最大值if lens (end-start1): # 如果本次的长度比记录的回文的长度也就是end-start1大进行替换# 需要注意的是已经知道了位置i,不管是以i为中心扩展了长为lens的回文还是# 以i和i1的空隙为中心扩展了长为lens的回文。下面的start和end的计算方法都成立start i - math.floor((lens - 1) / 2) end i math.floor(lens/2)print(start, :, end)
print(s[start:end1])这里时间复杂度并没有改变但是我们的空间复杂度变成了O(1)。但是也带来了明显的缺陷那就是只能求的第一个出现的最优解。 额如果把 if lens (end-start1) 改为 if lens (end-start1)那么能求最后出现的最优解。这两个算法不论在空间、结果上有什么不同它们的时间复杂度都是相同的接下来就分析一下“马拉车”算法该算法把时间复杂度降到了线性范围内。额请见下篇博客。
PS很多人都分析了马拉车算法但是也阻挡不了我征服它的步伐。相信自己对它一定有独到的见解。
