5. 最长回文子串
5. 最长回文子串
🟠 🔖 双指针
字符串
动态规划
🔗 力扣
LeetCode
题目
Given a string s
, return the longest palindromic substring in s
.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
1 <= s.length <= 1000
s
consist of only digits and English letters.
题目大意
给你一个字符串 s
,找到 s
中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
s
仅由数字和英文字母组成。
解题思路
思路一:中心扩展法
找回文串的难点在于,回文串的的长度可能是奇数也可能是偶数,解决问题的核心是以每个字符或两个相邻字符为中心,用左右指针向两边扩展,判断是否是回文串。遍历所有可能的中心,记录最长的回文串。
- 奇数长度的回文串: 以每个字符为中心,向两边扩展判断回文串。
- 偶数长度的回文串: 以每两个相邻字符的中心向两边扩展判断回文串。
复杂度分析
- 时间复杂度:
O(n^2)
,其中n
是字符串的长度。 - 空间复杂度:
O(1)
。
思路二:动态规划
动态规划法的思想是,利用已知的回文串信息推导出更长的回文串。
定义动态规划数组
dp
,其中dp[i][j]
表示字符串s
从索引i
到索引j
是否为回文串。状态转移方程为:
s[i] == s[j] && dp[i+1][j-1] == true
时,dp[i][j] = true
- 否则,
dp[i][j] = false
边界条件:
dp[i][i] = true
s[i] == s[i+1]
时,dp[i][i+1] = true
复杂度分析
- 时间复杂度:
O(n^2)
,其中n
是字符串的长度。 - 空间复杂度:
O(n^2)
。
代码
中心扩展法
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
const palindrome = (i, j) => {
while (i >= 0 && j < s.length && s[i] == s[j]) {
i--;
j++;
}
return s.substring(i + 1, j);
};
let res = '';
for (let i = 0; i < s.length; i++) {
let s1 = palindrome(i, i);
let s2 = palindrome(i, i + 1);
res = res.length > s1.length ? res : s1;
res = res.length > s2.length ? res : s2;
}
return res;
};
动态规划
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
const n = s.length;
let dp = new Array(n).fill(false).map((i) => new Array(n).fill(false));
let start = 0;
let end = 0;
// 初始化动态规划数组
for (let i = 0; i < n; i++) {
dp[i][i] = true;
if (i < n - 1 && s[i] == s[i + 1]) {
dp[i][i + 1] = true;
start = i;
end = i + 1;
}
}
// 对于长度为 2 的子串,我们在初始化动态规划数组时已经考虑到了,即 dp[i][i+1]。
// 因此,从长度为 3 的子串开始遍历,直到长度为 n 的子串,逐步填充动态规划数组。
for (let len = 3; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
if (s[i] == s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
start = i;
end = i + len - 1;
}
}
}
return s.substring(start, end + 1);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
214 | 最短回文串 | 字符串 字符串匹配 哈希函数 1+ | 🔴 | 🀄️ 🔗 | |
266 | 回文排列 🔒 | 位运算 哈希表 字符串 | 🟢 | 🀄️ 🔗 | |
336 | 回文对 | 字典树 数组 哈希表 1+ | 🔴 | 🀄️ 🔗 | |
516 | 最长回文子序列 | [✓] | 字符串 动态规划 | 🟠 | 🀄️ 🔗 |
647 | 回文子串 | 双指针 字符串 动态规划 | 🟠 | 🀄️ 🔗 | |
2472 | 不重叠回文子字符串的最大数目 | 贪心 双指针 字符串 1+ | 🔴 | 🀄️ 🔗 |