图TOOL 的博客

LeetCode题解：最长回文子串

题目描述：给你一个字符串 s，找到 s 中最长的回文子串。

解题思路

我们可以使用动态规划来解决这个问题，通过构建一个二维数组来记录子串是否为回文。

def longest_palindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1

    for i in range(n):
        dp[i][i] = True

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]
                if dp[i][j] and length > max_length:
                    start, max_length = i, length
    return s[start:start + max_length]

        

返回主页