Leetcode 5 最长回文子串

Time: 2019-08-05

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring

思路分析：用什么算法

使用的是中心线扩展法。

注意中心线扩展有两种情况，一种是以当前字符扩展，另一种是以两个字符之间的分界作为扩展。

需要写一个函数，用于计算两种扩展方式能够得到的最长的回文子串。

得到这样的函数后，就可以写出来查找最长的回文子串的算法了。

代码实现

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s or s == s[::-1]: # s[::-1]表示字符串的反向序列
            return s 
        res = ''
        for i in range(len(s)):
            tmp1 = self.getPalindrom(s, i, i)
            tmp2 = self.getPalindrom(s, i, i+1)
            if len(tmp1) > len(res):
                res = tmp1
            
            if len(tmp2) > len(res):
                res = tmp2
        return res
    
    def getPalindrom(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]

getPalindrom函数的写法中，若对称的字符相等时，才会让双指针背向扩展。可以结合简单样例来共同思考。

1.需要注意的地方

中心线扩展需要分成两个情况考量，但是拆分出来的函数getPalindrom是一样的。

2.可以优化的地方

用马拉车算法可以实现O(n)的时间复杂度。

时空复杂度分析

时间复杂度：O(n^2)
空间复杂度：O(1)

哪些题是类似的，做过的

动态规划解法

本题也可以用动态规划的方式来解。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ''
        n = len(s)
        is_palindrome = [[False] * n for _ in range(n)] # 二维数组
        
        # 对角线表示单个字符是不是回文子串
        for i in range(n):
            is_palindrome[i][i] = True
        
        for i in range(1, n):
            is_palindrome[i][i-1] = True
        
        start, longest = 0, 1
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                # 推导公式
                is_palindrome[i][j] = is_palindrome[i+1][j-1] and s[i] == s[j]
                if is_palindrome[i][j] and longest < length:
                    longest = length
                    start = i
        return s[start:start+longest]

性能并不比上面的算法要好。

END.