python最长回文串

可以使用动态规划算法来解决最长回文串问题。

具体来说，我们定义一个二维数组dp，其中dp[i][j]表示字符串s在[i, j]区间内的子串是否是回文串，当i=j时，只有一个字符，肯定是回文串，如果i=j+1，说明是相邻字符，此时需要判断s[i]是否等于s[j]，如果i和j不相邻，即i-j>=2时，除了判断s[i]和s[j]相等之外，dp[j+1][i-1]若为真，就是回文串。

代码如下：

def longest_palindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s

    # 定义二维dp数组
    dp = [[False] * n for _ in range(n)]

    # 初始化，每个单独的字符都是回文串
    for i in range(n):
        dp[i][i] = True

    # 记录回文串的左下标和长度
    start, max_len = 0, 1

    # 枚举区间长度
    for L in range(2, n + 1):
        # 枚举左边界
        for i in range(n):
            # 计算右边界
            j = L + i - 1
            if j >= n:  # 右边界越界，结束本次循环
                break

            if s[i] != s[j]:  # 首尾不相等，不是回文串
                dp[i][j] = False
            else:
                if j - i < 3:  # 长度为3及以下的子串，首尾相等即为回文串
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]  # 转移方程

            # 如果当前子串是回文串并且长度更长，则更新最长回文串的左下标和长度
            if dp[i][j] and j - i + 1 > max_len:
                start = i
                max_len = j - i + 1

    # 返回最长回文串
    return s[start:start + max_len]

例如，对于字符串"babad"，最长回文串为"bab"或"aba"，使用上述算法可以得到正确的答案。