题解 | 最长回文子串

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        n = len(A)
        if n<2:
            return n
        dp = [[False]*n for _ in range(n)]
        start, max_len = 0, 1
        for i in range(n):#长度为1的子串全部为回文串
            dp[i][i] = True
        for length in range(2,n+1):#遍历做有可能的长度
            for i in range(n-length+1):#当前长度下的可能开始坐标
                j = i+length-1#当前长度、开始坐标下的结束坐标
                if A[i]==A[j]:#如果当前坐标下两侧字符相同
                    if length==2 or dp[i+1][j-1]:#内侧字符相同，或长度为2
                        dp[i][j] = True
                        if length>max_len:
                            start, max_len = i, length
        return max_len#不仅可以求出长度，还可以求出最长回文串本身