跳至主要內容

5. 最长回文子串


5. 最长回文子串open in new window

🟠   🔖  双指针 字符串 动态规划  🔗 力扣open in new window LeetCodeopen in new window

题目

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;
};

相关题目

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