python如何實(shí)現(xiàn)對(duì)求解最長(zhǎng)回文子串的動(dòng)態(tài)規(guī)劃算法

這篇文章給大家分享的是有關(guān)python如何實(shí)現(xiàn)對(duì)求解最長(zhǎng)回文子串的動(dòng)態(tài)規(guī)劃算法的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

具體內(nèi)容如下

1、題目

給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為1000。

示例 1：

輸入: "babad"
輸出: "bab"

注意: "aba"也是一個(gè)有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

2、求解

對(duì)于暴力求解在這里就不再驁述了，著重介紹如何利用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。

關(guān)于動(dòng)態(tài)規(guī)劃的含義及用法，請(qǐng)參考鏈接，這篇文章通過(guò)漫畫(huà)的形式對(duì)動(dòng)態(tài)規(guī)劃算法進(jìn)行了詳細(xì)而又有風(fēng)趣的介紹。值得一看。

2.1 算法一

利用常規(guī)動(dòng)態(tài)規(guī)劃算法，即利用表來(lái)存儲(chǔ)每一中回文子串的可能。

基于動(dòng)態(tài)規(guī)劃的三要素對(duì)問(wèn)題進(jìn)行分析，可確定以下的狀態(tài)轉(zhuǎn)換方程：

其中f(i,j)表示當(dāng)s[i:j]子串是否是回文串。當(dāng)j-i<=1時(shí)，如果s[i] == s[j]則表示s[i:j]為回文串，及f(i,j) = true，否則f(i,j) = false。當(dāng)j-i > 1時(shí)，則判斷 s[i]、s[j]是否相等以及f(i+1, j-1)是否為true，即s[i+1:j-1]是否為回文串，如果為真，則f(i,j) = true

所以就需要一個(gè)n*n的二維矩陣用于存儲(chǔ)f(i,j)的值，其中 j in range(0, k)，i in range(0, j+1)，之所以是j+1是因?yàn)閕可以等于j。

python3代碼如下：

 k = len(s) # 計(jì)算字符串的長(zhǎng)度 
 matrix = [[0 for i in range(k)] for i in range(k)] # 初始化n*n的列表 
 logestSubStr = "" # 存儲(chǔ)最長(zhǎng)回文子串 
 logestLen = 0 # 最長(zhǎng)回文子串的長(zhǎng)度 
 
  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   # 此時(shí)f(i,j)置為true 
      if logestLen < j - i + 1: # 將s[i:j]的長(zhǎng)度與當(dāng)前的回文子串的最長(zhǎng)長(zhǎng)度相比 
       logestSubStr = s[i:j+1] # 取當(dāng)前的最長(zhǎng)回文子串 
       logestLen = j - i + 1 # 當(dāng)前最長(zhǎng)回文子串的長(zhǎng)度 
    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

 采用當(dāng)前算法，時(shí)間復(fù)雜度為O(n*n)，空間復(fù)雜度為O(n*n)，算法平均耗時(shí)大概5~7s

下面介紹空間復(fù)雜度為O(n)的算法。

2.2 算法二

算法二是由算法一改良而來(lái)，觀察算法一的執(zhí)行流程如下：

當(dāng)j>1時(shí)，判斷f(i,j)是否為回文子串的操作只與j-1時(shí)的的操作相關(guān)，即f(i,j) = g(f(i, j-1))，其中j>1，i in range(0, j+1)，所以接下來(lái)就變成求解g()函數(shù)了。   

用nlist存儲(chǔ)j情況下所有的子串是否為回文子串的標(biāo)志

用olist存儲(chǔ)j-1情況下所有的子串是否為回文子串的標(biāo)志

那么olist與nlist的關(guān)系是什么呢？

有上圖可知，nlist[i] = g(olist[i+1])

新的算法如下：

k = len(s) 
 olist = [0] * k # 申請(qǐng)長(zhǎng)度為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 # 當(dāng) j 時(shí)，第 i 個(gè)子串為回文子串 
      len_t = j - i + 1 
      if logestLen < len_t: # 判斷長(zhǎng)度 
       logestSubStr = s[i:j + 1] 
       logestLen = len_t 
    else: 
     if s[i] == s[j] and olist[i+1]: # 當(dāng)j-i>1時(shí)，判斷s[i]是否等于s[j]，并判斷當(dāng)j-1時(shí)，第i+1個(gè)子串是否為回文子串 
      nList[i] = 1 # 當(dāng) j 時(shí)，第 i 個(gè)子串為回文子串 
      len_t = j - i + 1 
      if logestLen < len_t: 
       logestSubStr = s[i:j + 1] 
       logestLen = len_t 
   olist = nList  # 覆蓋舊的列表 
   nList = [0] * k # 新的列表清空 
  return logestSubStr

 這樣新算法的空間復(fù)雜度就為O(2n)，即O(n)。算法平均耗時(shí)3s左右，而且該算法更符合動(dòng)態(tài)規(guī)劃的原理。

感謝各位的閱讀！關(guān)于“python如何實(shí)現(xiàn)對(duì)求解最長(zhǎng)回文子串的動(dòng)態(tài)規(guī)劃算法”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！