难度: Medium
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
Submission
运行时间: 1000 ms
内存: 15 MB
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) < 2:
return s
def expand(l, r):
while l < r:
if l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
else:
break
return s[l+1:r]
ans = ''
for i in range(len(s)):
# 奇数
l = i - 1
r = i + 1
k = expand(l, r)
if len(k) > len(ans):
ans = k
# 偶数
l = i - 1
r = i + 1 - 1
k = expand(l, r)
if len(k) > len(ans):
ans = k
return ans
Explain
这个题解使用了中心扩展法来寻找最长回文子串。对于字符串中的每个位置，以该位置为中心，向两边扩展，找到以该位置为中心的最长回文子串。需要考虑回文子串长度为奇数和偶数两种情况。最后返回所有找到的回文子串中最长的一个。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) < 2:
return s
def expand(l, r):
while l < r:
# 如果当前字符串是回文串，则继续向两边扩展
if l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
else:
break
# 返回找到的最长回文子串
return s[l+1:r]
ans = ''
for i in range(len(s)):
# 寻找以当前位置为中心的奇数长度回文串
l = i - 1
r = i + 1
k = expand(l, r)
if len(k) > len(ans):
ans = k
# 寻找以当前位置为中心的偶数长度回文串
l = i - 1
r = i + 1 - 1
k = expand(l, r)
if len(k) > len(ans):
ans = k
return ans
Explore
中心扩展法在解决最长回文子串问题时非常高效，因为它直接利用了回文的对称性质。与动态规划相比，中心扩展法的空间复杂度较低，为 O(1)，因为它不需要额外的存储空间来保存子问题的解。此外，中心扩展法的时间复杂度通常优于动态规划，尤其是在最坏情况下，动态规划需要 O(n^2) 的时间和空间复杂度。而中心扩展法的时间复杂度为 O(n^2)，但在实际应用中常常表现出更好的性能，因为并不是所有的中心都需要扩展到最大可能的长度。
在处理偶数长度的回文子串时，中心扩展法需要考虑两个连续字符作为中心点。具体来说，如果考虑索引 i 和 i+1 作为中心，这两个索引之间实际上没有字符，可以视为在两个字符之间有一个虚拟的中心。从这种虚拟的中心开始扩展，可以确保找到所有可能的偶数长度的回文子串。这种处理方式确保了不会遗漏任何偶数长度的回文子串，同时也很自然地融入了中心扩展法的框架中。
扩展函数在检测到不匹配的字符时立即停止确实可能存在边界调整的需求，但这通常不影响回文长度的正确性。函数在检测到不匹配时停止，而返回的子串是从 l+1 到 r-1（不包括 r），这恰好是最后一个匹配的有效回文子串。因此，尽管在实际实现中需要正确处理边界（例如，确保不越界），扩展停止的位置是正确的，无需额外调整。
奇数和偶数长度的回文子串具有不同的对称性质。奇数长度的回文中心是一个实际的字符，而偶数长度的回文中心是两个字符之间的虚拟位置。这种结构上的差异导致在寻找回文时必须分别处理。如果不区分处理，就无法准确地从字符串中心扩展出所有可能的回文子串，因为奇偶长度的中心点选取方式不同。因此，为了全面覆盖所有回文可能性，单独处理奇数和偶数长度的情况是必要的。