0005. 最长回文子串

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 上 从位置 ij 的子串 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)$。
本站总访问量  次  |  您是本站第  位访问者