Repository navigation
5.最长回文子串 #47
Description
如果一个字符串 aba 是一个回文串，那么在它的左右分别添加一个相同的字符 a，那么它一定还是一个回文串 aabaa。
我们可以用 dp[i][j] 表示 s 中从 i 到 j (包括 i 和 j) 是否可以形成回文串，将上面这段话翻译成代码，列出状态转移方程。
- dp[i][j] === true 是回文串
- dp[i][j] === false 不是回文串
状态转移方程
s[i] === s[j] && dp[i][j] = dp[i + 1][j - 1]
边界处理
需要考虑 j - i < 2 的情况，此时子串长度为 0 或 1。
例如：a，aa，对称点分别是字符本身和两个字符中间的虚拟点。
双重循环，不断向外延伸尝试得到可能的最大回文串长度。第一层倒着循环，是因为 dp[i] 依赖于 dp[i + 1]。
const longestPalindrome = function (s) {
const len = s.length
const dp = Array.from(new Array(len), () => new Array(len).fill(0))
let res = ''
for (let i = len - 1; i >= 0; i--) {
for (let j = i; j < len; j++) {
dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])
if (dp[i][j] && j - i + 1 > res.length) { // 符合条件时截取得到最长的回文串
res = s.slice(i, j + 1)
}
}
}
return res
}- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
Activity