题解 | #编号子回文I#

key：

1. 横纵字符串反序构建二维矩阵
2. 对角线计算dp，同时能保留最大长度与最大串的末尾索引
3. 利用最大串的末尾索引和最大长度可以找到对应的序列

class Solution:
    def longestPalindrome(self , s: str) -> str:
        s_ = s[::-1]
        lenth = len(s)
        dp = [[0] * lenth for _ in range(lenth)]
        for i in range(lenth):
            if s[i] == s_[0]:
                dp[i][0] = 1
            if s_[i] == s[0]:
                dp[0][i] = 1
        
        MAX = 1
        result_i = 0
        for i in range(1, lenth):
            for j in range(1, lenth):
                if s[i] == s_[j]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    if dp[i][j] > MAX:
                        MAX = dp[i][j]
                        result_i = i
        return s[result_i - MAX + 1: result_i + 1]