5. 最长回文子串
目录
题目
给你一个字符串 s，找到 s 中最长的回文子串。
解法
力扣第五题（Longest Palindromic Substring）要求找到给定字符串 s 中最长的回文子串。要解决这个问题，可以采用多种方法，如动态规划、中心扩展法等。我们可以使用中心扩展法来实现，这种方法的时间复杂度为 O(n²)，空间复杂度为 O(1)，适合处理中等长度的字符串。
中心扩展法思路：
- 回文的中心可以是一个字符（奇数长度回文），也可以是两个字符（偶数长度回文）。
- 遍历字符串中的每个字符，并尝试以该字符为中心向两侧扩展，找到尽可能长的回文子串。
- 每次扩展后更新当前最长回文子串的起始位置和长度。
C++代码实现：
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
if (s.empty()) return "";
int start = 0, maxLength = 1;
// Lambda 函数，用于从中心扩展
auto expandAroundCenter = [&](int left, int right) {
while (left >= 0 && right < s.length() && s[left] == s[right]) {
left--;
right++;
}
// 回文长度为 (right - 1) - (left + 1) + 1 = right - left - 1
int currentLength = right - left - 1;
if (currentLength > maxLength) {
maxLength = currentLength;
start = left + 1;
}
};
for (int i = 0; i < s.length(); i++) {
// 奇数长度回文
expandAroundCenter(i, i);
// 偶数长度回文
expandAroundCenter(i, i + 1);
}
return s.substr(start, maxLength);
}
};
int main() {
Solution solution;
string s = "babad";
cout << "Longest Palindromic Substring: " << solution.longestPalindrome(s) << endl;
return 0;
}
代码解释：
-
expandAroundCenter(int left, int right)：这是一个 lambda 函数，用于从中心扩展，检查左右字符是否相同，直到无法扩展为止。每次扩展后，比较当前找到的回文子串长度是否比之前的最长长度大，如果是则更新起始位置和长度。 -
两次扩展：
- 一次考虑以
i为中心的奇数长度回文。 - 一次考虑以
i和i + 1为中心的偶数长度回文。
- 一次考虑以
-
s.substr(start, maxLength)：返回从start开始、长度为maxLength的子串。
示例：
输入字符串为 "babad" 时，输出的最长回文子串可能是 "bab" 或 "aba"（两者都为合法答案）。
时间复杂度：
- O(n²)：我们遍历字符串中的每个字符，并从每个字符向两侧扩展，最多需要 O(n) 的时间，每次扩展的操作也是 O(n)。
中心扩展，以谁为中心？
以每个字符为中心，向两边扩展
for (int i = 0; i < s.length(); i++) {
// 奇数长度回文
expandAroundCenter(i, i);
// 偶数长度回文
expandAroundCenter(i, i + 1);
}
中心扩展法（Center Expansion Method）是一种常用的算法，专门用于解决寻找字符串中最长回文子串的问题。其核心思想是：每一个字符（或字符之间的空隙）都可以作为回文的“中心”，从这个中心向两边扩展，检查是否能形成回文子串。通过以每个可能的中心进行扩展，就能找到所有的回文子串，并在其中确定最长的回文子串。
什么是回文？
回文是指正着读和反着读都一样的字符串。例如，"aba" 和 "racecar" 都是回文。
中心扩展法的关键思想：
- 每个字符或每两个字符之间的间隙都可能是回文的中心。
- 对于每个中心，向左右两侧扩展，直到左右两侧的字符不相等为止，这样就能找到以该中心为基础的最长回文子串。
- 通过遍历所有可能的中心并进行扩展，最终可以找到最长的回文子串。
为什么需要考虑“间隙”？
因为回文子串的长度可以是奇数或偶数：
- 如果是奇数长度的回文（例如
"aba"），中心是单个字符。 - 如果是偶数长度的回文（例如
"abba"），中心是两个字符之间的间隙。
中心扩展法的算法步骤：
- 遍历字符串中的每个字符位置
i。 - 对于每个位置
i，考虑两种情况：- 奇数长度回文：以字符
i为中心，左右扩展。 - 偶数长度回文：以字符
i和i + 1之间的空隙为中心，左右扩展。
- 奇数长度回文：以字符
- 在每一次扩展中，检查是否能继续扩展，如果左右两侧的字符相等则继续扩展；否则，停止扩展。
- 记录每次扩展的回文子串长度，并更新最长回文子串的位置和长度。
- 最终得到最长的回文子串。
中心扩展法的复杂度：
- 时间复杂度：每次扩展的操作最多需要检查一次字符串的一半，所以整体复杂度是 (O(n^2))，其中
n是字符串的长度。 - 空间复杂度：由于只需要几个额外的变量来记录位置和长度，因此空间复杂度为 (O(1))。
示例：
假设字符串 s = "babad"。
-
以
i = 0（字符'b'）为中心：- 奇数长度扩展得到回文
"b"。 - 偶数长度扩展不成功。
- 奇数长度扩展得到回文
-
以
i = 1（字符'a'）为中心：- 奇数长度扩展得到回文
"bab"。 - 偶数长度扩展不成功。
- 奇数长度扩展得到回文
-
以
i = 2（字符'b'）为中心：- 奇数长度扩展得到回文
"aba"。 - 偶数长度扩展不成功。
- 奇数长度扩展得到回文
-
以
i = 3（字符'a'）为中心：- 奇数长度扩展得到回文
"a"。 - 偶数长度扩展不成功。
- 奇数长度扩展得到回文
-
以
i = 4（字符'd'）为中心：- 奇数长度扩展得到回文
"d"。 - 偶数长度扩展不成功。
- 奇数长度扩展得到回文
最终，最长回文子串是 "bab" 或 "aba"，长度为 3。
总结：
中心扩展法通过将每个字符（或字符之间的间隙）作为回文的中心，从中向外扩展来寻找最长的回文子串。它是一种直观、易于实现的算法，在时间复杂度为 (O(n^2)) 的情况下，可以高效解决回文子串问题。
如何存储最大长度下对应的字符串？
存储第一个字符的索引，加上最大长度就是
int start = 0, maxLength = 1;
return s.substr(start, maxLength);
s.substr(start, maxLength)怎么使用？
通过 s.substr(start, maxLength)，我们从原字符串 s 中提取出从 start 开始，长度为 maxLength 的子串，这就是最长的回文子串。
代码中为什么start = left + 1;
在这段代码中，start = left + 1 是为了正确计算当前找到的回文子串的起始位置。让我们详细解释为什么需要这样做：
代码背景：
在中心扩展法中，我们从中心向左右扩展，判断是否可以继续扩展回文。扩展过程中的左边界和右边界的索引分别由 left 和 right 来控制。当我们发现左右不再匹配时，扩展停止，而此时 left 和 right 已经超出了回文子串的实际边界。
为什么是 start = left + 1？
当左右扩展不再满足回文条件时，left 和 right 的位置都已经超出回文子串的实际范围。例如，当 left 向左移动时，会减小到一个不符合条件的值，right 向右移动时会增大到一个不符合条件的值。因此，当扩展停止时：
- 左边界的正确位置应该是
left + 1，因为left的最后一次减小已经超出了回文的范围。 - 右边界就是
right - 1，而长度可以通过right - left - 1计算。
举例说明：
假设字符串 s = "babad"，我们以 i = 1（字符 'a'）为中心进行扩展：
-
初始：
left = 1, right = 1，当前中心是字符'a'。
-
第一次扩展：
- 左右扩展：
left = 0, right = 2，s[0] == s[2]（即'b' == 'b'），继续扩展。 - 现在回文子串是
"bab"。
- 左右扩展：
-
第二次扩展：
- 左右扩展：
left = -1, right = 3，left超出了字符串的左边界，扩展停止。
- 左右扩展：
此时，left = -1，right = 3，而实际的回文子串在 left + 1 = 0 到 right - 1 = 2 之间，即 "bab"。因此，我们需要将 start 设为 left + 1，即 start = 0，表示回文子串从索引 0 开始。
总结：
start = left + 1 是因为扩展过程中 left 会超出实际回文子串的左边界，所以需要加 1 来调整到正确的起始位置。
Lambda 函数怎么使用？
在你的代码中，使用了 Lambda 函数 来简化代码结构和逻辑处理。Lambda 函数是一种轻量级的、匿名的函数，在 C++11 引入，用于在代码中定义简单的内联函数，而无需单独声明和定义。
Lambda 函数的语法：
auto expandAroundCenter = [&](int left, int right)
[捕获列表](参数列表) -> 返回类型 { 函数体 };
组成部分：
-
捕获列表
[捕获列表]：- 捕获列表用于指定当前作用域中哪些变量会被 Lambda 捕获使用。
- 例如
[&]表示按引用捕获所有变量，[=]表示按值捕获所有变量。
-
参数列表
(参数列表)：- 与普通函数一样，指定 Lambda 的输入参数。
-
返回类型
-> 返回类型（可选）：- 可以显式指定返回类型。如果可以根据函数体推导返回类型，则可以省略。
-
函数体
{ 函数体 }：- 定义 Lambda 函数的操作逻辑，即函数体。
Lambda 函数在代码中的使用：
在代码中，你定义了一个用于从字符串中心向两侧扩展的 Lambda 函数 expandAroundCenter：
auto expandAroundCenter = [&](int left, int right) {
while (left >= 0 && right < s.length() && s[left] == s[right]) {
left--;
right++;
}
int currentLength = right - left - 1;
if (currentLength > maxLength) {
maxLength = currentLength;
start = left + 1;
}
};
解析：
-
捕获列表
[&]：- 捕获了当前作用域的所有变量（如
start、maxLength、s等）按引用传递，使得 Lambda 函数内部可以修改这些变量的值。
- 捕获了当前作用域的所有变量（如
-
参数列表
(int left, int right)：- 这个 Lambda 函数接收两个参数
left和right，它们分别表示中心扩展的左右边界。
- 这个 Lambda 函数接收两个参数
-
返回类型：
- 返回类型未显式声明，C++ 能根据 Lambda 函数体的内容自动推导返回类型。因为这个 Lambda 函数没有返回值，所以推导返回类型为
void。
- 返回类型未显式声明，C++ 能根据 Lambda 函数体的内容自动推导返回类型。因为这个 Lambda 函数没有返回值，所以推导返回类型为
-
函数体：
- 首先使用
while循环，检查从left到right的字符是否相等，并不断向外扩展，直到不满足回文条件或超出字符串边界。 - 当扩展结束时，计算当前回文子串的长度，并检查它是否比之前找到的最大长度
maxLength更大。如果是，则更新maxLength和起始位置start。
- 首先使用
为什么使用 Lambda 函数？
Lambda 函数可以在需要定义简单函数时避免写额外的函数声明，尤其是当这个函数只在局部使用时。例如在该代码中，expandAroundCenter 只在一个特定的算法步骤中使用，并且依赖了许多外部变量，如 start、maxLength 和 s，使用 Lambda 可以让这些变量自动捕获并使用，而不必将它们显式传递给一个普通的函数。这使得代码更加简洁、清晰。
Lambda 函数的优势：
- 简洁性：可以在需要时内联定义，而不需要提前声明函数。
- 作用域管理：Lambda 函数可以轻松捕获所在作用域的变量，不需要通过参数传递，简化了代码。
- 局部使用：适合定义只在局部使用的小型函数，不必污染全局命名空间。
总结：
Lambda 函数是 C++ 中的一个非常强大的工具，用于简化代码。在你的代码中，expandAroundCenter 是一个典型的使用案例，简化了回文扩展的实现，并捕获了外部变量来动态调整回文子串的起始位置和长度。
原文地址：https://blog.csdn.net/qq_43920838/article/details/143029214
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！