题目要求
-
思路：
- 如果 a 是回文字符串，那么如果 a 的左侧字符 = a 的右侧字符，【a 左侧字符 +a+ a 的右侧字符】也是一个回文串
- 同理，如果 bab 是回文字符串，那么 如果最左侧 b 的左侧字符 = 最右侧的 b 的右侧字符，那么【最左侧 b 的左侧字符 + bab + 最右侧的 b 的右侧字符】也是一个回文字符串
-
所以能够编写一个函数 get_str，给定已知回文子字符串的最小下标和最右下标，而后横向扩散去寻找回文字符串。
- 例如 字符串 s = “babad”，b 的下标为 2，b 为一个回文子字符串，那么把 2 作为字符串的左下标 left，2 同时作为字符串的右下标 right，让函数 get_str 去向左向右寻找，如果 left > 0 and right < len(s) and s[left] == s[right]，就让 left – 1，right + 1，而后在比拟 s[left-1] 与 s[right+1] 是否相等，且下标不超过 0 和 len(s)
-
那么如何确定要给 get_str 什么样的下标呢，能够通过遍历字符串 s
-
每遍历到一个字符，有两种状况
- 1、这个字符是核心字符，例如 bab，a 就是核心字符，那么给 get_str 的左下标和右下标都是 a 的下标
- 2、这个字符和这个字符的下一个字符独特组成核心字符，例如，baab，那么给 get_str，左侧 a 的下标作为左下标，右侧 a 的下标作为右下标
-
- 还须要有两个变量，start，end，用来保留以后最长子回文串的左下标和右下标，如果 get_str 找到比以后长期保留的子字符串更长的回文串，要更新 start 和 end，最初返回 s[start,end + 1]（因为 s[start:end] 会不算上 end）
- 外围代码
class Solution:
def longestPalindrome(self, s: str) -> str:
def get_str(left, right, s):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# 返回 left+ 1 和 right- 1 是因为最初一次 while 循环会对 left 多减一，对 right 多 +1，这时的 left 和 right 左右会多各多算一个字符
return left + 1, right - 1
start, end = 0, 0
for i in range(len(s)):
# 两种状况
left1, right1 = get_str(i, i, s)
left2, right2 = get_str(i, i + 1, s)
# 如果搜寻到比以后回文子字符串更长的，就要更新
if right1 - left1 > end -start:
start, end = left1, right1
if right2 - left2 > end -start:
start, end = left2, right2
return s[start:end + 1]残缺代码
class Solution:
def longestPalindrome(self, s: str) -> str:
def get_str(left, right, s):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
start, end = 0, 0
for i in range(len(s)):
left1, right1 = get_str(i, i, s)
left2, right2 = get_str(i, i + 1, s)
if right1 - left1 > end -start:
start, end = left1, right1
if right2 - left2 > end -start:
start, end = left2, right2
return s[start:end + 1]