Python3最長(zhǎng)回文子串算法示例
更新時(shí)間：2019年03月04日 11:12:38 作者：gxnustc
這篇文章主要介紹了Python3最長(zhǎng)回文子串算法,結(jié)合實(shí)例形式分析了暴力算法及動(dòng)態(tài)規(guī)劃算法判斷最長(zhǎng)回文子串的相關(guān)操作技巧,需要的朋友可以參考下
本文實(shí)例講述了Python3最長(zhǎng)回文子串算法。分享給大家供大家參考，具體如下：
1. 暴力法
思路：對(duì)每一個(gè)子串判斷是否回文
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) == 1:
return s
re = s[0]
for i in range(0,len(s)-1):
for j in range(i+1,len(s)):
sta = i
end = j
flag = True
while sta < end:
if s[sta] != s[end]:
flag = False
break
sta += 1
end -= 1
if flag and j-i+1 > len(re):
re = s[i:j+1]
return re
提交結(jié)果：超出時(shí)間限制
2. 動(dòng)態(tài)規(guī)劃法
思路：
m[i][j]標(biāo)記從第i個(gè)字符到第j個(gè)字符構(gòu)成的子串是否回文，若回文值為True，否則為False.
初始狀態(tài) s[i][i] == True，其余值為False.
當(dāng) s[i] == s[j] and m[i+1][j-1] == True 時(shí)，m[i][j] = True
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
k = len(s)
matrix = [[False for i in range(k)] for j in range(k)]
re = s[0:1]
for i in range(k):
for j in range(k):
if i==j:
matrix[i][j] = True
for t in range(1,len(s)): #分別考慮長(zhǎng)度為2~len-1的子串（長(zhǎng)串依賴短串的二維數(shù)組值）
for i in range(k):
j = i+t
if j >= k:
break
if i+1 <= j-1 and matrix[i+1][j-1]==True and s[i] == s[j]:
matrix[i][j] = True
if t+1 > len(re):
re = s[i:j+1]
elif i+1 == j and j-1 == i and s[i] == s[j]:
matrix[i][j] = True
if t+1 > len(re):
re = s[i:j+1]
return re
執(zhí)行用時(shí)：8612 ms
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
詳解python 拆包可迭代數(shù)據(jù)如tuple, list
拆包是指將一個(gè)結(jié)構(gòu)中的數(shù)據(jù)拆分為多個(gè)單獨(dú)變量中。下面通過(guò)本文給大家介紹python 拆包可迭代數(shù)據(jù)如tuple, list的相關(guān)資料，需要的朋友參考下吧2017-12-12
今天小編就為大家分享一篇解決Python安裝后pip不能用的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-06-06
這篇文章主要為大家詳細(xì)介紹了python使用webdriver爬取微信公眾號(hào)信息，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-08-08
這篇文章主要介紹了Python類和實(shí)例的屬性機(jī)制原理詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03
Python有三大神器，一個(gè)是裝飾器，一個(gè)是迭代器、生成器，最后一個(gè)就是今天文章的主角 -- 「上下文管理器」。上下文管理器在日常開(kāi)發(fā)中的作用是非常大的，可能有些人用到了也沒(méi)有意識(shí)到這一點(diǎn)2022-12-12
本文主要介紹了Python3 re.search()方法的具體使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
這篇文章主要介紹了python連接mysql并提交mysql事務(wù)的示例,需要的朋友可以參考下2014-03-03
Python實(shí)現(xiàn)csv文件(點(diǎn)表和線表)轉(zhuǎn)換為shapefile文件的方法
這篇文章主要介紹了Python實(shí)現(xiàn)csv文件(點(diǎn)表和線表)轉(zhuǎn)換為shapefile文件的方法,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-10-10
這篇文章主要介紹了Python中os.path用法,實(shí)例分析了os.path的各種常用方法,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-01-01
Pygame游戲開(kāi)發(fā)之太空射擊實(shí)戰(zhàn)敵人精靈篇
相信大多數(shù)8090后都玩過(guò)太空射擊游戲，在過(guò)去游戲不多的年代太空射擊自然屬于經(jīng)典好玩的一款了，今天我們來(lái)自己動(dòng)手實(shí)現(xiàn)它，在編寫(xiě)學(xué)習(xí)中回顧過(guò)往展望未來(lái)，下面開(kāi)始講解敵人精靈的使用2022-08-08