LC 5、最长回文子串
题目描述
这是LeetCode 上的 5、最长回文子串，难度为 中等
给你一个字符串 s,找到 s中最长的回文字串。
示例：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
- 1 <= s.length <= 1000
s仅由数组和英文字母（大写和/或小写）组成
本题有时间限制，我们如果使用枚举子串的方法必然超时，所以我们如果要枚举暴力，也应该做出更优美的暴力算法
朴素解法
枚举字符串 s中的每一位，作为回文串的中心点，左右进行扩展，直到达到边界或者不满足回文串定义为止。
当我们有一个简单的实现方法之后，需要从题目的数据规模，计算机的处理速度和实现方法的计算量出发，判断这样的作法是否会超时。
由于字符串长度最多只有1000， 而我们的实现方法是O(n^2)，因此我们算法计算量在10e6， 是在计算机每秒的处理范围内的。
首先枚举回文串的中心i，然后分情况向两边扩展边界，直到达到边界或者不满足回文子串定义为止：
- 回文串长度为奇数， 判断s[i - k] == s[i + k]，k = 1, 2, 3, ...
- 回文串长度为偶数， 判断s[i - k] == s[i + k - 1], k = 1. 2, 3, ...
代码：
class Solution {
public:
string longestPalindrome(string s) {
int start = 0 , end = 0;
for(int i = 0 ; i < s.size(); i++){
auto [l1, r1] = getstr(s, i, i);
auto [l2, r2] = getstr(s, i, i + 1);
if(end - start < r1 - l1){
end = r1;
start = l1;
}
if(end - start < r2 - l2){
end = r2;
start = l2;
s }
}
return s.substr(start, end - start + 1);
}
pair<int, int> getstr(string& s, int l , int r){
while(l >= 0 && r < s.size() && s[l] == s[r]){
l--;
r++;
}
return {l + 1, r - 1};
}
};
- 时间复杂度：先枚举了
s中的每个字符作为回文串的中心点，再从中心点左右扩展，最多扩展到边界。复杂度为 O(n^2) - 空间复杂度：O(1)
Manacher 算法(扩展)--三叶姐yyds(摘录自宫水三叶的刷题日记)
这是一个比较冷门的算法，使用范围也比较单一，只能用于解决【回文串】问题。Manacher是【回文串】问题的最优解。
Manacher算法较长，为了避免回文串长度奇偶问题的分情况讨论，在这里会原字符进行了处理，在边界和字符之间插入占位符。
使用了这样的技巧之后，当非占位字符作为回文串的中心时，对应了回文串长度为奇数的情况；当占位字符作为回文串的中心时，对应了回文串长度为偶数的情况。
class Solution {
public:
int expand(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left;
++right;
}
return (right - left - 2) / 2;
}
string longestPalindrome(string s) {
int start = 0, end = -1;
string t = "#";
for (char c: s) {
t += c;
t += '#';
}
t += '#';
s = t;
vector<int> arm_len;
int right = -1, j = -1;
for (int i = 0; i < s.size(); ++i) {
int cur_arm_len;
if (right >= i) {
int i_sym = j * 2 - i;
int min_arm_len = min(arm_len[i_sym], right - i);
cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
} else {
cur_arm_len = expand(s, i, i);
}
arm_len.push_back(cur_arm_len);
if (i + cur_arm_len > right) {
j = i;
right = i + cur_arm_len;
}
if (cur_arm_len * 2 + 1 > end - start) {
start = i - cur_arm_len;
end = i + cur_arm_len;
}
}
string ans;
for (int i = start; i <= end; ++i) {
if (s[i] != '#') {
ans += s[i];
}
}
return ans;
}
};
Label：模拟，回文串