5.最长回文子串

链接

LeeCode-5-最长回文子串

参考

知乎

Git

题目描述

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

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

示例 2：
输入: "cbbd"
输出: "bb"

实现(python3)

把每个字母当成回文串的中心

class Solution(object):
    def longestPalindrome(self, s):
        n = len(s)
        self.res = ""
        def helper(i,j):
            while i>=0 and j<n and s[i]==s[j]:
                i-=1
                j+=1
                if len(self.res)<=j-i-1:
                    self.res = s[i+1:j]
        for i in range(n):
            helper(i,i)
            helper(i,i+1)
        return self.res

把每个字母当成回文串的结束

class Solution():
    def longestPalindrome(self, s):
        if not s:
            return ""
        max_len = 1
        n = len(s)
        start = 0
        for i in range(1,n):
            even = s[i-max_len:i+1]
            odd = s[i-max_len-1:i+1]

            if i-max_len-1 >= 0 and odd==odd[::-1]:
                start = i-max_len
                max_len += 2
            if i-max_len >= 0 and even==even[::-1]:
                start = i-max_len
                max_len += 1

        return s[start:start + max_len]

dp[i][j]表示字符串从j到i是否是为回文串,即当s[j] == s[i]如果dp[i-1][j+1]也是回文串,那么字符串从j到i也是回文串,即dp[i][j]为真

class Solution():
    def longestPalindrome(self, s):
        if not s:
            return ""
        max_len = float("-inf")
        n = len(s)
        res = ""
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            for j in range(i, -1, -1):
                if s[i] == s[j] and (i-j < 2 or dp[i-1][j+1]):
                    dp[i][j] = 1
                if dp[i][j] and max_len <= i-j +1:
                    print("i,j",i,j)
                    res = s[j:i+1]
                    max_len = i-j+1

        return res

注释：
float("inf") # 正无穷
float("-inf") # 负无穷