LeetCode 0005 - Longest Palindromic Substring
# Hints
- 暴力枚举
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a string , find the longest palindromic substring in . You may assume that the maximum length of is .
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
# 题意
给定一个字符串,求其最长回文子串。如果有多个答案,返回任意一个均可。
# 题解
暴力枚举回文子串的中心点,向左右延展到最大长度,更新答案即可。
注意长度为偶数的回文子串,此时中心点在两个下标之间,处理起来有些麻烦。可以直接处理,也可以用如下方法解决:在原串的左右边界和每两个字符之间插入分隔符,例如串 abaab
会变成 #a#b#a#a#b#
,这样就不需要特殊处理偶数了。
最长回文子串问题用Manacher算法求解是最优的,时间复杂度为 ,但本题的时间并无要求,故此处不予展开。
细节问题:
注意特判空串。
注意不能忘记在左右边界插入分隔符,否则例如串
abb
变成a#b#b
就可能会计算错误。
# AC代码
class Solution {
public:
string longestPalindrome(string s) {
// 特判
if (s.empty()) {
return string("");
}
// 预处理
string str;
str += '#';
for (int i = 0; i < s.length(); i ++) {
str += s[i];
str += '#';
}
// 枚举
int maxlen = 0;
int index = 0;
for (int i = 0; i < str.length(); i ++) {
int len = solve(str, i);
if (maxlen < len) {
maxlen = len;
index = i;
}
}
// 获取答案
string res;
for (int i = index - maxlen + 1; i <= index + maxlen - 1; i ++) {
if (str[i] != '#') {
res += str[i];
}
}
// 返回
return res;
}
// 获取当前中心的回文半长
int solve(const string & str, int index) {
int len = 0;
while (index - len >= 0 && index + len < str.length()) {
if (str[index - len] == str[index + len]) {
len ++;
} else {
break;
}
}
return len;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01