【算法题】5. 最长回文子串-力扣(LeetCode)
【算法题】5. 最长回文子串-力扣(LeetCode)
1.题目
下方是力扣官方题目的地址
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的 回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
2.题解
思路
比较容易想到的且容易理解的就是中心扩展法
就是遍历一遍这个字符串，以你遍历到的字符为中心向外扩展，如果两个目标相等就继续扩展，直到不相等为止。
扩展的时候需要分两种情况：目标字符串是奇数还是偶数
然后考虑到一些边界情况，这题便是解决了
python代码
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
def f(a,b):
if len(a)>len(b):return a # 函数f:哪个字符串长度大返回哪个字符串
else:return b
if len(s)==1:return s
ans,a,b='','',''
for i in range(len(s)):
p,k=0,0
while i-p>=0 and i+p<len(s) and s[i-p]==s[i+p]: # 目标串为奇数时
a=s[i-p:i+p+1]
p+=1
while i-k>=0 and i+1+k<len(s) and s[i-k]==s[i+1+k]: # 目标串为偶数时
b=s[i-k:i+2+k]
k+=1
ans=f(f(a,ans),b) # 维护答案
return ans
3.结语
本人资历尚浅，发博客主要是记录与学习，欢迎大佬们批评指教！大家也可以在评论区多多交流，相互学习，共同成长。