5. Longest Palindromic Substring
5. Longest Palindromic Substring
题目
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. 最短回文串](https://leetcode.com/problems/shortest-palindrome)
- [🔒 Palindrome Permutation](https://leetcode.com/problems/palindrome-permutation)
- [336. 回文对](https://leetcode.com/problems/palindrome-pairs)
- [516. 最长回文子序列](https://leetcode.com/problems/longest-palindromic-subsequence)
- [647. 回文子串](https://leetcode.com/problems/palindromic-substrings)
- [2472. 不重叠回文子字符串的最大数目](https://leetcode.com/problems/maximum-number-of-non-overlapping-palindrome-substrings)