题解 | #编号子回文I#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 定义一个二维数组 dp，其中 dp[i][j] 表示从编号 i 到编号 j 的子串是否是回文串。对于每个子串 s[i:j]，我们有两种情况：
2. 如果s[i]=s[j]，那么它可能是回文串，取决于 s[i+1:j−1] 是否也是回文串；
3. 如果 s[i]=s[j]，那么它一定不是回文串。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return string字符串
#
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""
        dp = [[0] * n for _ in range(n)]
        start, ans = 0, 1
        for i in range(n):
            dp[i][i] = 1
            if i < n - 1 and s[i] == s[i + 1]:
                dp[i][i + 1] = 1
                start, ans = i, 2
        for k in range(3, n + 1):
            for i in range(n - k + 1):
                j = i + k - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = 1
                    start, ans = i, k
        return s[start : start + ans]