0005. 最长回文子串 #
- 标签:字符串、动态规划
- 难度:中等
题目大意 #
描述:给定一个字符串 s
。
要求:找到 s
中最长的回文子串。
说明:
- 回文串:如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
- $1 \le s.length \le 1000$。
s
仅由数字和英文字母组成。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 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:复杂度分析 #
- 时间复杂度:$O(n^2)$,其中 $n$ 是字符串的长度。
- 空间复杂度:$O(n^2)$。