描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
示例 3：
输入：s = “a”
输出：“a”
示例 4：
输入：s = “ac”
输出：“a”
提示：
1 <= s.length <= 1000 s 仅由数字和英文字母（大写和/或小写）组成
Related Topics
- 字符串
- 动态规划
👍 4626
👎 0
题解
python
复杂度n^2(调用了find方法,其实算n^3)，慢，准备再优化
"""
3:56 PM info
解答成功:
执行耗时:780 ms,击败了71.07% 的Python3用户
内存消耗:14.9 MB,击败了96.09% 的Python3用户
"""
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
max_str = ""
max_len = 0
break_idx = 0
all_len = len(s)
for idx, val in enumerate(s):
p_idx = idx
t_idx = s.find(val, p_idx + 1) # 核心思路是暴力获取每个位置挨个区间内查找
while t_idx > 0:
t_len = t_idx + 1 - idx
if t_len == 2 and t_len > max_len:
max_str = s[idx: t_idx+1]
break_idx = all_len - t_len
max_len = t_idx + 1 - idx
elif t_len > max_len:
t_str = s[idx: t_idx+1]
if t_str == t_str[::-1]:
max_str = t_str
max_len = t_idx + 1 - idx
break_idx = all_len - t_len
t_idx = s.find(val, t_idx + 1)
if t_idx < 0 and not max_str:
max_str = val
break_idx = all_len - 1
continue
if idx == break_idx:
break
return max_str
先排出空字符串、单个字符、整个串都是回文的情况，再对每次移动指针，每次扫描指针及前两个字符（有一个字符是中心点）和指针前一个字符（两个字符是中心）的情况，然后从中心开始指针每次向后移动一个字符，相当于检查中心+两边各一个字符的是否是回文，逐步扩大扫描
"""
3:32 PM info
解答成功:
执行耗时:52 ms,击败了99.76% 的Python3用户
内存消耗:15.2 MB,击败了51.69% 的Python3用户
"""
class Solution:
def longestPalindrome(self, s: str):
if len(s) < 2 or s == s[::-1]:
return s
res = s[0]
maxlen = 1
for i in range(1, len(s)):
odd = s[i - maxlen - 1: i + 1] # 一个字符中心
even = s[i - maxlen: i + 1] # 两个字符中心
if odd and odd == odd[::-1]:
res = odd
maxlen += 2
continue
if even == even[::-1]:
res = even
maxlen += 1
continue
return res
