python如何实现对求解最长回文子串的动态规划算法

这篇文章给大家分享的是有关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左右，而且该算法更符合动态规划的原理。

感谢各位的阅读！关于“python如何实现对求解最长回文子串的动态规划算法”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！