[LeetCode] 5. Longest Palindromic Substring题解

问题描述

给定一个字符串 s,找出其中最长的回文子字符串,假设 s 的最大长度为 1000。

例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是正确的答案

例 2:

Input: "cbbd"
Output: "bb"

问题难度

Medium

解题思路

注意到回文的对称性特点,我们只需要在遍历 s 的过程中,假设每一个字符都是回文的中心,对于每一个回文中心,我们不断向两边扩展,同时检测其对称性,找出该回文的边界,并记录其长度,最终,当遍历完 s 之后,我们便检测了 s 中所有的回文,当然就可以得到 s 中最长的回文子字符串。这种方法的时间复杂度为 O(n^2)​。

需要注意的是,回文有两种形式:单中心和双中心,所以我们在遍历每个字符时,不仅要把当前字符当做单中心回文的中心,还要将当前字符和下一个字符当做双中心回文的中心,并分别以这两个中心向两边扩展。

全部代码如下:

class Solution():
    def expand(self, left, right, s):
        """
        expand from middle point
        """
        if right >= len(s) or s[left] != s[right]:
            return 0

        while left-1 >= 0 and right+1 < len(s) and s[left-1] == s[right+1]:
            left -= 1
            right += 1

        return right + 1 - left

    def longest_palindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ""

        middle = 0
        max_len = 0
        for i in range(len(s)):
            len1 = self.expand(i, i, s)
            len2 = self.expand(i, i+1, s)
            longer = max(len1, len2)
            if longer > max_len:
                max_len = longer
                middle = i

        begin = middle-int((max_len-1)/2)
        return s[begin:begin+max_len]

原题链接