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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Python实现判断一个字符串是否包含子串的方法总结

    本文实例总结了Python实现判断一个字符串是否包含子串的方法.分享给大家供大家参考,具体如下: 1.使用成员操作符 in >>> s='nihao,shijie' >>> t='nihao' >>> result = t in s >>> print result True 2.使用string模块的find()/rfind()方法 >>> import string >>> s='nihao,s

  • 详解Python最长公共子串和最长公共子序列的实现

    最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题.解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0.然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置. def find_lcsubstr(s1, s2): m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵,为方便后续计算,比字符串长度

  • Python字符串中查找子串小技巧

    惭愧啊,今天写了个查找子串的Python程序被BS了- 如果让你写一个程序检查字符串s2中是不是包含有s1.也许你会很直观的写下下面的代码: 复制代码 代码如下: #determine whether s1 is a substring of s2 def isSubstring1(s1,s2):     tag = False     len1 = len(s1)     len2 = len(s2)     for i in range(0,len2):         if s2[i] =

  • Python实现统计给定字符串中重复模式最高子串功能示例

    本文实例讲述了Python实现统计给定字符串中重复模式最高子串功能.分享给大家供大家参考,具体如下: 给定一个字符串,如何得到其中重复模式最高的子字符串,我采用的方法是使用滑窗机制,对给定的字符串切分,窗口的大小从1增加到字符串长度减1,将所有的得到的切片统计结果,在这里不考虑单个字符的重复模式,好了,很简单看具体实现: #!usr/binenv python #encoding:utf-8 ''''' __Author__:沂水寒城 统计一个给定字符串中重复模式数量得到最高重复模式串 '''

  • Python实现针对给定字符串寻找最长非重复子串的方法

    本文实例讲述了Python实现针对给定字符串寻找最长非重复子串的方法.分享给大家供大家参考,具体如下: 问题: 给定一个字符串,寻找其中最长的重复子序列,如果字符串是单个字符组成的话如"aaaaaaaaaaaaa"那么满足要求的输出就是a 思路: 这里的思路有两种是我能想到的 (1)从头开始遍历字符串,设置标志位,在往后走的过程中当发现和之前标志位重合的时候就回头检查一下这个新出现的子串是否跟前面字符串或者前面字符串的子串相同,相同则记录该子串并计数加1,直至处理完毕 (2)利用滑窗切

  • python实现求最长回文子串长度

    给定一个字符串,求它最长的回文子串长度,例如输入字符串'35534321',它的最长回文子串是'3553',所以返回4. 最容易想到的办法是枚举出所有的子串,然后一一判断是否为回文串,返回最长的回文子串长度.不用我说,枚举实现的耗时是我们无法忍受的.那么有没有高效查找回文子串的方法呢?答案当然是肯定的,那就是中心扩展法,选择一个元素作为中心,然后向外发散的寻找以该元素为圆心的最大回文子串.但是又出现了新的问题,回文子串的长度即可能是基数,也可能好是偶数,对于长度为偶数的回文子串来说是不存在中心元

  • Python简单实现查找一个字符串中最长不重复子串的方法

    本文实例讲述了Python简单实现查找一个字符串中最长不重复子串的方法.分享给大家供大家参考,具体如下: 刚结束的一个笔试题,很简单,不多说简单贴一下具体的实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出来一个字符串中最长不重复子串 ''' def find_longest_no_repeat_substr(one_str): ''''' 找出来一个字符串中最长不重复子串 ''' res_list=[] le

  • 在Python中实现替换字符串中的子串的示例

    假如有个任务: 给定一个字符串,通过查询字典,来替换给定字符中的变量.如果使用通常的方法: >>> "This is a %(var)s" % {"var":"dog"} 'This is a dog' >>> 其实可以使用string.Template类来实现上面的替换 >>> from string import Template >>> words = Template

  • Python利用正则表达式匹配并截取指定子串及去重的方法

    本文实例讲述了Python利用正则表达式匹配并截取指定子串及去重的方法.分享给大家供大家参考.具体如下: import re pattern=re.compile(r'\| (\d+) \| (\d+) \|') numset=set() all=''' | 29266795 | 533 | | 29370116 | 533 | | 29467495 | 533 | | 29500404 | 533 | | 29500622 | 533 | | 29515964 | 530 | | 295160

  • Python中判断子串存在的性能比较及分析总结

    起步 对于子串搜索,Python提供了多种实现方式:in, find, index, __contains__,对其进行性能比较: import timeit def in_(s, other): return other in s def contains(s, other): return s.__contains__(other) def find(s, other): return s.find(other) != -1 def index(s, other): try: s.index

随机推荐