LeetCode5. 最长回文子串（双指针、中心扩展算法）

1、题目描述 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 2、代码详解 class Solution(object): def longestPalindrome(self, s): res = "" for i in range(len(s)): # 法一 # # odd case, like "aba" # tmp = self.helper(s, i, i) # if len(tmp) > len(re 在LeetCode的第5题《最长回文子串》中，目标是找到给定字符串` s `中的最长回文子串。回文串是指正读反读都能读通的字符串，例如 "aba" 和 "abba" 都是回文串。本题要求的解决方案需在字符串长度不超过1000的限制内进行。 解决问题的关键在于运用双指针和中心扩展算法。这里有两个主要的思路，分别称为“法一”和“法二”。 **法一** 是通过两个指针` l `和` r `从中间向外扩展。首先考虑奇数长度的情况，即从一个字符开始，然后考虑偶数长度的情况，即从两个相邻的字符开始。这两个情况可以通过调用辅助函数` helper `来处理，该函数接收字符串` s `以及中心点的左右坐标` l `和` r `。在` helper `函数内部，使用一个` while `循环，不断检查` s[l] `和` s[r] `是否相等，如果相等则扩大搜索范围，直到遇到不匹配的字符或超出了字符串边界。` helper `函数返回以` l `和` r `为中心的最长回文子串。 **法二** 是将法一中的两种情况合并，同时调用` helper `函数处理从单个字符和相邻的两个字符出发的情况，并利用` max `函数根据长度来选取最长的回文子串。这使得代码更为简洁。 在实际实现时，定义一个类` Solution `，其中包含主方法` longestPalindrome `和辅助方法` helper `。在` longestPalindrome `中，遍历字符串的所有字符，对于每个字符，都尝试以它为中心进行扩展，找到可能的最长回文子串。最后返回最长的那个回文子串。 以下是一个具体的例子： ```python class Solution: def longestPalindrome(self, s): res = "" for i in range(len(s)): 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 return s[l + 1:r] ``` 在给出的示例中，输入字符串` s = 'babad' `，输出的结果是` 'bab' `，这是该字符串中的最长回文子串。 这种双指针中心扩展的算法时间复杂度为O(n^2)，空间复杂度为O(1)，因为它只需要常数级别的额外空间。尽管存在更高效的动态规划解决方案，但对于本题的规模，这种方法已经足够高效。