python實現(xiàn)對求解最長回文子串的動態(tài)規(guī)劃算法

更新時間：2018年06月02日 14:56:43 作者：bailang_zhizun

這篇文章主要為大家詳細(xì)介紹了python實現(xiàn)對求解最長回文子串的動態(tài)規(guī)劃算法，具有一定的參考價值，感興趣的小伙伴們可以參考一下

基于Python實現(xiàn)對求解最長回文子串的動態(tài)規(guī)劃算法，具體內(nèi)容如下

1、題目

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

示例 1：

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

注意: "aba"也是一個有效答案。

示例 2：

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

2、求解

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

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

2.1 算法一

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

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

其中f(i,j)表示當(dāng)s[i:j]子串是否是回文串。當(dāng)j-i<=1時，如果s[i] == s[j]則表示s[i:j]為回文串，及f(i,j) = true，否則f(i,j) = false。當(dāng)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]的長度與當(dāng)前的回文子串的最長長度相比 
       logestSubStr = s[i:j+1] # 取當(dāng)前的最長回文子串 
       logestLen = j - i + 1 # 當(dā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)前算法，時間復(fù)雜度為O(n*n)，空間復(fù)雜度為O(n*n)，算法平均耗時大概5~7s

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

2.2 算法二

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

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

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

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

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

有上圖可知，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 # 當(dāng) 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]: # 當(dāng)j-i>1時，判斷s[i]是否等于s[j]，并判斷當(dāng)j-1時，第i+1個子串是否為回文子串 
      nList[i] = 1 # 當(dāng) 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

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

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: