python算法題之《最長回文子串》
題目要求
給定一個字符串 s术吝，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000羞酗。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案顷霹。
示例 2：
輸入: "cbbd"
輸出: "bb"
代碼及解析
class Solution:
def longestPalindrome(self, s):
# 用于存放每個字母出現(xiàn)的位置
dic = {}
# 回文判斷開始位置
flag = 0
# 當(dāng)前處于字符串的位置
i = 0
# 返回值
ans =""
while i < len(s):
# 當(dāng)前字母不在字典中
if s[i] not in dic:
# 用于存放重復(fù)字母的下標如s='ababa'則dic={a:[0,2,4],b:[1,3]}
dic[s[i]] = []
# 當(dāng)前字母在字典中
if s[i] in dic:
# 將當(dāng)前字母的位置添加到指定字母的列表中
dic[s[i]].append(i)
# 遍歷該字母的位置列表
for flag in dic[s[i]]:
# 如果是回文贸诚，判斷是否更換ans矾瑰，然后跳出循環(huán)衷佃，直到找到回文字符串欺冀，最后一個肯定是，因為flag=i
if s[flag:i+1] == s[flag:i+1][::-1]:
# 如果長度大于上一個ans试幽，ans=當(dāng)前回文字符串
if len(ans) < len(s[flag:i+1]):
ans = s[flag:i+1]
break
# 字符串下標位置加一
i += 1
# 返回最長回文字符串
return ans
結(jié)果
image.png
