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)。

---

思路二：动态规划

1. 定义 dp[i][j]：

   • dp[i][j] = true 表示 s[i:j]（从 i 到 j 的子串）是回文串。
   • dp[i][j] = false 表示 s[i:j] 不是回文串。

2. 状态转移：

   • s[i] == s[j] 时：
     • 长度为 1 或 2：s[i:j] 一定是回文（i == j 或 j - i == 1）。
     • 长度大于 2：s[i:j] 只有在 dp[i+1][j-1] == true 时才是回文。

3. 初始化：

   • 单个字符 dp[i][i] = true。

4. 遍历顺序：

   • j 先递增，确保 dp[i+1][j-1] 在 dp[i][j] 之前计算完毕。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是字符串的长度，双层循环填充 dp。
• 空间复杂度：O(n^2)，存储 dp 数组。

代码

中心扩展法

/**
 * @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;
};

动态规划

var longestPalindrome = function (s) {
	const n = s.length;
	const dp = Array(n)
		.fill()
		.map(() => Array(n).fill(false));
	let start = 0,
		end = 0;

	for (let j = 0; j < n; j++) {
		dp[j][j] = true;
		for (let i = 0; i < j; i++) {
			if (s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
				dp[i][j] = true;
				if (j - i > end - start) {
					start = i;
					end = j;
				}
			}
		}
	}
	return s.slice(start, end + 1);
};

相关题目

题号	标题	题解	标签	难度	力扣
214	最短回文串		字符串 字符串匹配 哈希函数 1+	🔴	🀄️ 🔗
266	回文排列 🔒		位运算 哈希表 字符串	🟢	🀄️ 🔗
336	回文对		字典树 数组 哈希表 1+	🔴	🀄️ 🔗
516	最长回文子序列	[✓]	字符串 动态规划	🟠	🀄️ 🔗
647	回文子串		双指针 字符串 动态规划	🟠	🀄️ 🔗
2472	不重叠回文子字符串的最大数目		贪心 双指针 字符串 1+	🔴	🀄️ 🔗