0005. 最长回文子串 #

标签：字符串、动态规划
难度：中等

题目大意 #

描述：给定一个字符串 s。

要求：找到 s 中最长的回文子串。

说明：

回文串：如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
$1 \le s.length \le 1000$。
s 仅由数字和英文字母组成。

示例：

示例 1：

1
2
3


输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2


输入：s = "cbbd"
输出："bb"

解题思路 #

思路 1：动态规划 #

主要是定义状态转移方程，以及更新最长回文子串的位置和长度。初始化一个 n * n 大小的布尔类型数组 dp[][] ，dp[i][j] 表示字符串 s 上从位置 i 到 j 的子串 s[i...j] 是否是一个回文串。

可以很容易的看出来，当子串只有 1 位或 2 位的时候，如果 s[i] == s[j]，该子串为回文子串， dp[i][j] = (s[i] == s[j])。

如果子串大于 2 位，则如果 s[i + 1...j - 1] 是回文串，且 s[i] == s[j]，则 s[i...j] 也是回文串，dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]。

当判断完 s[i: j] 是否为回文串时，判断并更新最长回文子串的起始位置和最大长度。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return s

        dp = [[False for _ in range(n)] for _ in range(n)]
        max_start = 0
        max_len = 1

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

思路 1：复杂度分析 #

时间复杂度：$O(n^2)$，其中 $n$ 是字符串的长度。
空间复杂度：$O(n^2)$。