最长回文子串

5. 最长回文子串

难度⭐⭐

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

示例 1：

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

示例 2：

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

思路

暴力，判断每个子串是否为回文串

#暴力法
#判断每个子串是否为回文串
def longestPalindrome(s: str):
    if not s:
        return ""
    maxlen,start = 0,0
    for i in range(1,len(s)):
        for j in range(i):
            if isValid(s,j,i):
                maxlen = max(maxlen,i-j+1)
                start = j
    return s[start:start+maxlen]

def isValid(s,left,right):
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

动态规划

#动态规划
# dp[i][j] = dp[i+1][j-1] && (s[i]==s[j])
class Solution:
    def longestPalindrome(self, s: str) -> str:
        #动态规划
        # dp[i][j] = dp[i-1][j-1] && (s[i]==s[j])
        if not s:
            return ""
        n = len(s)
        dp = [[False]*n for _ in range(n)]
        ans = ""
        
        for l in range(1,n+1):#枚举长度
            for i in range(n):#枚举起始位置
                j = i+l-1
                if j >= len(s):
                    break
                if l == 1:
                    dp[i][j] = True
                elif l == 2:
                    dp[i][j] = (s[i]==s[j])
                else:
                    dp[i][j] = (dp[i+1][j-1] and s[i]==s[j])
                if dp[i][j] and l > len(ans):
                    ans = s[i:j+1]
        return ans

中心扩展

#中心扩展
class Solution:
    def longestPalindrome(self, s: str) -> str:
        start,end = 0,0
        n = len(s)
        for i in range(n):
            #偶数长度的中心扩展
            left1,right1 = self.expand(s,i,i+1)
            #奇数长度的中心扩展
            left2,right2 = self.expand(s,i,i)
            
            if right1-left1 > end-start:
                start,end = left1,right1
            if right2-left2 > end-start:
                start,end = left2,right2
        return s[start:end+1]

    def expand(self,s,left,right):
        while left>=0 and right<len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left+1,right-1

最长回文子串

5. 最长回文子串

推荐阅读