LeetCode 5. 最长回文子串（双指针与中心扩展法）
5星
- 浏览量: 0
- 大小:None
- 文件类型：PDF
简介：
本题讲解如何使用双指针及中心扩展法寻找字符串中最长的回文子串，适合对算法和数据结构感兴趣的读者。
在LeetCode的第5题《最长回文子串》中，目标是找到给定字符串` s `中的最长回文子串。回文串是指正读反读都能读通的字符串，例如 aba 和 abba 都是回文串。本题要求的解决方案需在字符串长度不超过1000的情况下进行。
解决问题的关键在于运用双指针和中心扩展算法。这里有两个主要的方法：**法一** 通过两个指针` l `和` r `从中间向外扩展，首先考虑奇数长度的情况（即以一个字符为中心），然后是偶数长度的情况（即以相邻的两个字符为起点）。这两种情况可以通过调用辅助函数` helper `来处理。在该辅助函数中使用一个循环不断检查当前指针所指向的字符是否相等，并根据结果调整指针位置，直到找到最长回文子串或遇到不匹配为止。
**法二** 则是将上述两种情况进行合并，在每个可能的位置同时调用` helper `处理单个字符和相邻两个字符的情况。通过比较这两种情况下的回文长度来选择最优解，使得代码更为简洁高效。
在实现时定义一个类` Solution `，其中包含主方法` longestPalindrome `以及辅助函数` helper `。主方法遍历字符串中的每个位置，并尝试以此为中心进行扩展搜索以找到可能的最长回文子串；最后返回整个过程中发现的最大长度的回文子串。
以下是一个具体的实现：
```python
class Solution:
def longestPalindrome(self, s):
res =
for i in range(len(s)):
# 奇数情况和偶数情况分别调用helper函数，并通过max选择最长的结果。
res = max(self.helper(s, i, i), self.helper(s, i, i + 1), res, key=len)
return res
def helper(self, s, l, r):
# 在边界条件内，向两边扩展寻找回文子串
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
# 返回以l和r为中心的最长回文字符串（注意循环结束时已经超出边界）
return s[l + 1:r]
```
对于输入` s = babad `，该代码会输出结果为` bab `,这是给定字符串中的一个最长回文子串。
这种双指针中心扩展算法的时间复杂度为O(n^2)，空间复杂度为O(1)。尽管存在更高效的动态规划解决方案，但对于本题的规模来说这种方法已经足够高效。
全部评论 (0)
