Python3最長回文子串算法示例
本文實(shí)例講述了Python3最長回文子串算法。分享給大家供大家參考，具體如下：
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)): #分別考慮長度為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)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
這篇文章主要介紹了python3?queue多線程通信，??Queue???對(duì)象已經(jīng)包含了必要的鎖，所以你可以通過它在多個(gè)線程間多安全地共享數(shù)據(jù)，更多相關(guān)內(nèi)容需要的朋友可以參考一下下文文章內(nèi)容2022-07-07
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 Scrapy爬蟲框架的相關(guān)知識(shí)，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-02-02
python 實(shí)現(xiàn)將小圖片放到另一個(gè)較大的白色或黑色背景圖片中
今天小編就為大家分享一篇python 實(shí)現(xiàn)將小圖片放到另一個(gè)較大的白色或黑色背景圖片中，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-12-12
在本篇文章里我們給大家整理了關(guān)于python線程里哪種模塊比較適合的相關(guān)知識(shí)點(diǎn)，需要的朋友們可以學(xué)習(xí)下。2020-08-08
這篇文章主要為大家詳細(xì)介紹了Python實(shí)現(xiàn)通訊錄功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
python讀取.mat文件及將變量存為.mat文件的詳細(xì)介紹
這篇文章主要給大家介紹了關(guān)于python讀取.mat文件及將變量存為.mat文件的詳細(xì)介紹,?mat文件是matlab的數(shù)據(jù)存儲(chǔ)的標(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ì)，對(duì)大家的學(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