Python3最長回文子串算法示例
本文實(shí)例講述了Python3最長回文子串算法。分享給大家供大家參考,具體如下:
1. 暴力法
思路:對每一個(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. 動態(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)): #分別考慮長度為2~len-1的子串(長串依賴短串的二維數(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)典教程》
希望本文所述對大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
python爬蟲指南之xpath實(shí)例解析(附實(shí)戰(zhàn))
在進(jìn)行網(wǎng)頁抓取的時(shí)候,分析定位html節(jié)點(diǎn)是獲取抓取信息的關(guān)鍵,目前我用的是lxml模塊,下面這篇文章主要給大家介紹了關(guān)于python爬蟲指南之xpath實(shí)例解析的相關(guān)資料,需要的朋友可以參考下2022-01-01
python 實(shí)現(xiàn)將小圖片放到另一個(gè)較大的白色或黑色背景圖片中
今天小編就為大家分享一篇python 實(shí)現(xiàn)將小圖片放到另一個(gè)較大的白色或黑色背景圖片中,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
python讀取.mat文件及將變量存為.mat文件的詳細(xì)介紹
這篇文章主要給大家介紹了關(guān)于python讀取.mat文件及將變量存為.mat文件的詳細(xì)介紹,?mat文件是matlab的數(shù)據(jù)存儲的標(biāo)準(zhǔn)格式,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-06-06
Python字符串處理實(shí)現(xiàn)單詞反轉(zhuǎn)
這篇文章主要為大家詳細(xì)介紹了Python字符串處理實(shí)現(xiàn)單詞反轉(zhuǎn)的方法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-06-06
Pytorch數(shù)據(jù)拼接與拆分操作實(shí)現(xiàn)圖解
這篇文章主要介紹了Pytorch數(shù)據(jù)拼接與拆分操作實(shí)現(xiàn)圖解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04
Python實(shí)現(xiàn)隨機(jī)生成算術(shù)題的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何利用Python實(shí)現(xiàn)隨機(jī)生成算術(shù)題的功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-04-04

