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),因为它只需要常数级别的额外空间。尽管存在更高效的动态规划解决方案,但对于本题的规模,这种方法已经足够高效。
- 粉丝: 9
- 资源: 892
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
评论0