【每日一题】LeetCode - 最长回文子串

2024/10/23 14:13:21 来源：https://blog.csdn.net/qq_37945670/article/details/143161063 浏览: 次关键词：【每日一题】LeetCode - 最长回文子串

在字符串相关的算法题中，寻找最长回文子串是一个经典且富有挑战性的题目。本篇将详细分析并推导两种有效的解决方案：动态规划法和中心扩展法。

题目描述

给定一个字符串 s，我们需要找到 s 中最长的回文子串。回文是指正着读和反着读都相同的字符串。例如，输入 "babad" 时，输出可以是 "bab" 或者 "aba"；输入 "cbbd" 时，输出为 "bb"。

解题思路

方法一：动态规划

如果你不了解什么是动态规划，或者时空复杂度，请参考以下内容：

【数据结构】动态规划：揭开算法优化的秘密
【数据结构】时间复杂度和空间复杂度是什么？

1. 定义状态： 我们使用一个二维布尔数组 dp，其中 dp[i][j] 表示字符串 s 从索引 i 到 j 的子串是否是回文。

2. 状态转移方程：

s[i] == s[j]

且：j - i <= 1（即当子串长度为1时），则 dp[i][j] = true，因为此时其只有1个或两个字母，且字母相同，构成回文。

dp[i + 1][j - 1] == true（即如果去掉首尾字符的子串也是回文，因为你观察一个回文字符会发现，如果一个字符是回文那么当你去除其首尾仍然是回文，这样我们按照动态规划的思想，对之前的计算结果进行计算，之后避免重复计算就可以减少时间复杂度），则 dp[i][j] = true。

3. 其他条件：

所有单个字符的子串都是回文，因此 dp[i][i] = true。
两个相同字符组成的子串也是回文，即 dp[i][i+1] = (s[i] == s[i+1])。

4. 实现代码：

class Solution {
public:string longestPalindrome(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int result = 0;string str;for (int i = s.length() - 1; i >= 0; --i) {for (int k = i; k < s.length(); ++k) {if (s[i] == s[k] && (k - i <= 1 || dp[i + 1][k - 1])) {dp[i][k] = true;if (k - i >= result) {result = k - i;str = s.substr(i, k - i + 1);}}}}return str;}
};

5. 时间复杂度： O(n²)，空间复杂度为 O(n²)。

方法二：中心扩展法

1. 原理： 每个回文可以视为围绕中心展开的。我们可以考虑两种情况：

以单个字符为中心（奇数长度回文，从单个字符开始左右定义两个指针，每次向外扩展，直到达到left == 0 || right == s.size() - 1边界，然后记录长度）。
以两个相同字符为中心（偶数长度回文，这种情况比较适用与两个相同字母在一起，因为此时她们就构成回文了，如果只使用单个字符做为中心，那么--left != --right是绝对成立的）。

2. 扩展过程： 从每个中心开始，逐步向外扩展，比较左右字符是否相等，直到不能再扩展为止。

3. 实现代码：

class Solution {
public:string longestPalindrome(string s) {string res;for (int i = 0; i < s.length(); ++i) {int r1 = maxLength(s, i, i); // 奇数长度回文int r2 = maxLength(s, i, i + 1); // 偶数长度回文res = res.length() >= r1 * 2 - 1 ? res : s.substr(i - r1 + 1, r1 * 2 - 1);res = res.length() >= r2 * 2 ? res : s.substr(i - r2 + 1, r2 * 2);}return res;}int maxLength(string s, int left, int right) {int r = 0;while (left >= 0 && right < s.length() && s[left] == s[right]) {left--;right++;r++;}return r;}
};