5. 最长的回文子串 - 从递归到动态编程的逐步优化
题目
给你一个字符串 s
,找到 s
中最长的回文子串。
示例 1:
输入: s = "babad"
输出: "bab"
解释: "aba" 同样是符合题意的答案。
示例 2:
输入: s = "cbbd"
输出: "bb"
示例 3:
输入: s = "a"
输出: "a"
示例 4:
输入: s = "ac"
输出: "a"
提示:
1 <= s.length <= 1000
-
s
仅由数字和英文字母(大写和/或小写)组成
递归
根据回文串的性质,可以从外边一层层往里面去对比,只要发现有哪一层的字符是不相等,就可以确定这不是一个回文子串.
我们可以只保存回文子串的左右索引,最后返回时从字符串中根据左右索引取出即可.
function longestPalindrome(s: string): string {
const n = s.length
const helper = (i: number, j: number): boolean => {
if (i === j) return true
if (s[i] !== s[j]) return false
if (i + 1 === j) return true
return helper(i + 1, j - 1)
}
let [left, right] = [0, 1]
for (let i = 0; i < n - 1; i++) {
for (let j = n - 1; j > i; j--) {
if (helper(i, j) && j - i + 1 > right - left) [left, right] = [i, j + 1]
}
}
return s.slice(left, right)
}
- 时间复杂度:
- 空间复杂度:
记忆化递归
直接递归的复杂度是 ,我们可以通过添加缓存,优化递归内部的时间复杂度
function longestPalindrome(s: string): string {
const n = s.length
const cache: boolean[][] = new Array(n).fill(0).map(() => [])
const helper = (i: number, j: number): boolean => {
if (cache[i][j] !== undefined) return cache[i][j]
if (i === j) return true
if (s[i] !== s[j]) return false
if (i + 1 === j) return true
cache[i][j] = helper(i + 1, j - 1)
return cache[i][j]
}
let [left, right] = [0, 1]
for (let i = 0; i < n - 1; i++) {
for (let j = n - 1; j > i; j--) {
if (helper(i, j) && j - i + 1 > right - left) [left, right] = [i, j + 1]
}
}
return s.slice(left, right)
}
- 时间复杂度:
- 空间复杂度:
动态规划
将上面的记忆化递归转成动态规划
需要注意的点是遍历的方向,递归的时候,调用栈帮我们保存了信息,所以我们可以从外边一层层往里面调用,然后在从最里面一层层返回,而使用动态规划时,就需要从最里面先计算,然后外边根据里面的状态来确定自己的状态.有两种遍历的方向,从后往前或者从前往后遍历都可以,其中 j 只需要遍历到 i 为止即可,另外一边是完全对称的.
我们选择从前往后遍历,i 从 0 开始到 s.length,j 从 0 到 i.
- 状态:
dp[i][j]
表示子串s[j..i]
(这里有包含 i 和 j 在内) 是否为回文 - 转移方程:
dp[i][j] = s[i]===s[j] && dp[i-1][j+1]
- 边界:
-
dp[i][i]=true
单个字符都是回文子串 - 会有一种特殊情况,比如
cbbd
,当 i=2,j=1 时,两个都为 b 是相等的,但是dp[i-1][j+1]
却是 undefined,所以上面的转移方程会返回 false,但实际上bb
却是符合回文子串的要求的,所以需要特殊处理,这里我们使用??
来处理,将 undefined 重置为 true
-
function longestPalindrome(s: string): string {
const n = s.length
let [left, right] = [0, 1]
const dp: boolean[][] = new Array(n).fill(0).map(() => [])
for (let i = 0; i < n; i++) {
dp[i][i] = true
for (let j = 0; j < i; j++) {
dp[i][j] = s[i] === s[j] ? dp[i - 1]?.[j + 1] ?? true : false
if (dp[i][j] && i - j + 1 > right - left) [left, right] = [j, i + 1]
}
}
return s.slice(left, right)
}
- 时间复杂度:
- 空间复杂度:
优化
通过研究转移方程,只有为 true 的状态会进行转移,所以可以不用将 j 从 0 遍历到 i,而只要保存之前为 true 的状态,之后通过遍历为 true 的状态,在进行判断 s[i]
是否等于 s[j]
即可,这样会更快一些.当然如果遇到一些比较极端的例子,还是需要全部遍历一遍的,比如全是 a 的字符串 aaaaaaaaaa
.
另外这样遍历的话,就无法获取 j 这个变量,状态就不能只是存是否为回文子串这样的布尔值,而需要存能让我们找到需要比对的 j 的值,这里可以选择存和当前字符组成回文子串的另一侧的索引,或者存回文子串的长度也可以,两者都能通过计算获取 j 的信息.下面的代码中保存的是对应的索引.
function longestPalindrome(s: string): string {
const n = s.length
let [left, right] = [0, 1]
const dp: number[][] = new Array(n).fill(0).map(() => [])
for (let i = 0; i < n; i++) {
dp[i].push(i)
dp[i].push(i + 1)
// if (s[i] === s[i - 1]) {
// dp[i].push(i - 1)
// ;[left, right] = [i - 1, i + 1]
// }
// 这里原本是需要用上面的代码对 `cbbd` 这样的例子进行额外的处理
// 不过通过 `dp[i].push(i + 1)` 可以省去额外的代码,直接集成到下面的循环中
for (const j of dp[i - 1] ?? []) {
if (s[i] === s[j - 1]) {
dp[i].push(j - 1)
if (i - j + 2 > right - left) [left, right] = [j - 1, i + 1]
}
}
}
return s.slice(left, right)
}
- 时间复杂度:
- 空间复杂度:
空间优化
上面的动态规划中,每次 i 的状态只与 i-1 有关,所以可以进行空间优化,使用两个一维数组来保存状态
function longestPalindrome(s: string): string {
const n = s.length
let [left, right] = [0, 1]
let pre: number[] = []
let cur: number[] = [0, 1]
for (let i = 0; i < n; i++) {
for (const j of pre) {
if (s[i] === s[j - 1]) {
cur.push(j - 1)
if (i - j + 2 > right - left) [left, right] = [j - 1, i + 1]
}
}
;[cur, pre] = [[i + 1, i + 2], cur]
}
return s.slice(left, right)
}
- 时间复杂度:
- 空间复杂度:
本篇文章只是为了研究如何从记忆化搜索转移到动态规划的过程,关于本题还有其他的解,比如
中心扩展算法
,以及时间复杂度为更优秀的 的Manacher 算法
等等.感兴趣的同学可以查看官方题解,以及题解区的其他题解.
上一篇: 5.最长的回文子串
下一篇: 如何在 Go 中测试软件包?