5. Longest Palindromic Substring

🟠   🔖  字符串 动态规划  🔗 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. 最短回文串
• 🔒 Palindrome Permutation
• 336. 回文对
• 516. 最长回文子序列
• 647. 回文子串
• 2472. 不重叠回文子字符串的最大数目

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