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

示例 1：

輸入: "babad"

輸出: "bab"

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

示例 2：

輸入: "cbbd"

輸出: "bb"

思考這個問題第一是從List兩邊考慮，先找到兩個相同的點， 然后各像中心移動1步。這個方法被PASS的原因是遇到輸入“aaabaaaa”時，兩邊同時移動則只能返回“aaaa”

第二次從回文子串的中心考慮，先假設List中每一個點ii都有回文子串，接下來驗證l[ii-1]和 l[ii+1]是否相同，如果相同就繼續驗證l[ii-2]和 l[ii+2]。對比所有結果，返回最大的子串。

class Solution:

def longestPalindrome(self, s):

""":type s: str:rtype: str"""

l=list(s)

length = len(l)

if length == 0:

return ""

if length == 1:

return s

temp=[]

result = []

i = 0

ii = 0

j = 1

flag = True

while ii < length:

i = ii - 1

j = ii + 1

while j < length and l[ii] == l[j]:

j = j + 1

temp = l[ii:j]

while (i>=0 and j<=length-1 and l[i] == l[j]):

temp = l[i:j+1]

i = i - 1

j = j + 1

if len(temp) > len(result):

result = temp

ii = ii + 1

if len(result) == 0:

return l[0]

return "".join(result)

時間復雜度是O(n^2)，不知道是不是算錯了，因為結果此方法速度在最后10%中。

這里提供一個大神的O(n)解法，用到了倒敘list對比。

class Solution:

def longestPalindrome(self, s):

"""

:type s: str

:rtype: str

"""

# 如果字符串長度小于2或者s等于它的倒序，則直接返回s

if len(s) < 2 or s == s[::-1]:

return s

n = len(s)

# 定義起始索引和最大回文串長度，odd奇，even偶

start, maxlen = 0, 1

# 因為i=0的話必然是不可能會有超過maxlen情況出現，所以直接從1開始

for i in range(1, n):

# 取i及i前面的maxlen+2個字符

odd = s[i - maxlen - 1:i + 1] # len(odd)=maxlen+2

# 取i及i前面的maxlen+1個字符

even = s[i - maxlen:i + 1] # len(even)=maxlen+1

if i - maxlen - 1 >= 0 and odd == odd[::-1]:

start = i - maxlen - 1

maxlen += 2

continue

if i - maxlen >= 0 and even == even[::-1]:

start = i - maxlen

maxlen += 1

return s[start:start + maxlen]

總結

以上是生活随笔為你收集整理的最长回文子串python_最长回文子串（Python）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。