LeetCode | 最长回文子串

分类：双指针/字符串

题目#

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

1
输入：s = "babad"
2
输出："bab"
3
解释："aba" 同样是符合题意的答案。

示例 2：

1
输入：s = "cbbd"
2
输出："bb"

讲解#

回文串以中心向两侧对称，所以枚举每个位置当中心，向两边扩展比较。

关键点：回文中心有两种——奇数长度是单个字符 (i, i)，偶数长度是相邻两字符中间 (i, i + 1)。两种都要试。

expand(left, right) 从中心向两侧扩展，只要左右字符相等就继续外扩，直到不相等或越界。因为循环结束时左右指针已经多走了一步，所以切片取 s[left + 1:right]。

说明： 官方分类在多维动态规划。我这种题解是双指针。

复杂度#

中心扩展法：
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)

代码#

源码#

1
class Solution:
2
    def longestPalindrome(self, s: str) -> str:
3
        def expand(left: int, right: int) -> str:
4
            while left >= 0 and right < len(s) and s[left] == s[right]:
5
                left -= 1
6
                right += 1
7
            return s[left + 1:right]
8

9
        ans = ""
10
        for i in range(len(s)):
11
            odd = expand(i, i)
12
            even = expand(i, i + 1)
13
            ans = max(ans, odd, even, key=len)
14
        return ans

测试#

1
sol = Solution()
2

3
assert sol.longestPalindrome("babad") in ("bab", "aba")
4
assert sol.longestPalindrome("cbbd") == "bb"
5
assert sol.longestPalindrome("a") == "a"
6
assert sol.longestPalindrome("ac") == "a"
7

8
print("PASS")

参考资料#

力扣原题：https://leetcode.cn/problems/longest-palindromic-substring/
题解参考：https://github.com/azl397985856/leetcode/blob/4183cbac/problems/5.longest-palindromic-substring.md

音乐

音乐

题目#

讲解#

复杂度#

代码#

源码#

测试#

参考资料#

文章分享

评论区

音乐

文章目录