python求字符串最长子串_Python刷题：最长回文子串（字符串）

题目描述：

给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为1000。

示例：

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

输入: "cbbd"
输出: "bb"

思路分析：

回文串的特点是以中心为轴对称，可以分为两种情况：以一个字符为中心，以两个字符为中心。所以我们可以枚举每一个字符和每两个字符的组合作为中心，然后向两边扩散，直到不能扩散为止。

代码实现：

class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) < 2:
return s
res = ""
for i in range(len(s)):
# 以一个字符为中心
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
# 以两个字符为中心
tmp = self.helper(s, i, i + 1)
if len(tmp) > len(res):
res = tmp
return res

def helper(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]

时间复杂度：O(n^2)
空间复杂度：O(1)