牛客_0017_中等_最长回文子串.md

最长回文子串

问题简述

求给定字符串中最长回文子串的长度。

最长回文子串_牛客题霸_牛客网

思路1：模拟中心扩散（推荐）

• 中心扩散直观，且不需要额外的空间，比动态规划的方法更好；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        n = len(A)
        
        def process(l, r):
            tmp = 1  # 使用一个变量保存已知的最大长度
            while l >= 0 and r < n:
                if A[l] != A[r]:
                    break
                tmp = r - l + 1
                l -= 1
                r += 1
            # return r - l + 1  # 直接返回有问题，无法判断最后一次是否匹配上
            return tmp
        
        ret = 1
        for i in range(len(A) - 1):
            # 同时处理 process(i, i), process(i, i + 1) 避免奇偶的讨论
            ret = max(ret, process(i, i), process(i, i + 1))
            
        return ret

思路2：动态规划

• dp 虽然能解，但是不够直观，且初始状态容易写错（相邻两个字符相同的情况）；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        n = len(A)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1
        
        start = 0
        length = 1
        for j in range(1, n):  # 子串的结束位置
            for i in range(j - 1, -1, -1):  # 子串的开始位置
                if i == j - 1:
                    dp[i][j] = 1 if A[i] == A[j] else 0
                else:
                    dp[i][j] = 1 if dp[i + 1][j - 1] and A[i] == A[j] else 0

                if dp[i][j]:
                    if j - i + 1 > length:
                        length = j - i + 1
                        start = i

        return length