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左右，而且该算法更符合动态规划的原理。