2019-03-30 Longest Palindromic S
一开始的想法是，定一个center和end，end往后移动，遇到不符合的把center往前移动，如此往复。但是这样忽略了第二种情况，就是偶数个数的情况。于是再加一次遍历，把偶数的找出来。代码如下：
class Solution {
public:
string longestPalindrome(string s) {
int start = 0, end = 0;
int nextStart = 0, nextEnd = 1;
while (nextEnd < s.size()) {
int savedStart = nextStart;
while (nextStart >= 0 && s[nextEnd] == s[nextStart]) {
if ((nextEnd - nextStart) > (end - start)) {
start = nextStart;
end = nextEnd;
}
nextEnd++, nextStart--;
}
nextStart = savedStart + 1;
nextEnd = nextStart + 1;
}
int center = 0, end2 = 0;
int nextCenter = 1; nextEnd = 2;
while (nextEnd < s.size()) {
while (nextCenter - (nextEnd - nextCenter) >= 0
&& s[nextEnd] == s[nextCenter - (nextEnd - nextCenter)]) {
if ((nextEnd - nextCenter) > (end2 - center)) {
center = nextCenter;
end2 = nextEnd;
}
nextEnd++;
}
nextCenter++;
nextEnd = nextCenter + 1;
}
if (end - start + 1 > 2 * (end2 - center) + 1) {
return s.substr(start, end - start + 1);
} else {
return s.substr(center - (end2 - center), 2 * (end2 - center) + 1);
}
}
};
成绩想不到还挺快的,这道题是中等以上的题第一次没有查别人的方法就得到不错的成绩：
Runtime:20 ms, faster than 82.97% of C++ online submissions forLongest Palindromic Substring.
Memory Usage:8.7 MB, less than 100.00% of C++ online submissions for Longest Palindromic Substring.
方案二：
看了别人的算法，有一种思路很特别，就是如果增加对重复的判断，就能同时处理奇数和偶数的情况了：
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() <= 1) return s;
int start = 0, end = 0;
int nextStart = 0, nextEnd = 0;
while (nextEnd < s.size()) {
while (nextEnd + 1 < s.size() && s[nextStart] == s[nextEnd + 1]) {
nextEnd++;
}
int savedStart = nextStart;
while (nextStart >= 0 && nextEnd < s.size() && s[nextEnd] == s[nextStart]) {
if ((nextEnd - nextStart) > (end - start)) {
start = nextStart;
end = nextEnd;
}
nextEnd++, nextStart--;
}
nextStart = savedStart + 1;
nextEnd = nextStart;
}
return s.substr(start, end - start + 1);
}
// center=0, end=0, nextEnd=2, nextCenter=1
//
};
跑了一下，速度差不多：
Runtime:16 ms, faster than 84.88% of C++ online submissions forLongest Palindromic Substring.
Memory Usage:8.8 MB, less than 99.74% of C++ online submissions for Longest Palindromic Substring.
但是还不到最快，肯定有能够提升的方法，因此上网差了一下，得到方案三
方案三：动态规划
一个子串是否回文数，可以由以下递推公式得出：
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() <= 1) return s;
int size = s.size();
int palindrome[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
palindrome[i][j] = 0;
}
}
int maxLength = 0;
int left = 0;
int right = 0;
for (int j = 0; j < size; j++) {
for (int i = 0; i <= j; i++) {
palindrome[i][j] = (s[i] == s[j] && (j - i < 2 || palindrome[i + 1][j - 1]));
if (palindrome[i][j] && j - i + 1 > maxLength) {
maxLength = j - i + 1;
left = i;
right = j;
}
}
}
return s.substr(left, right - left + 1);
}
};
但是这个动态规划的速度还挺慢的：
Runtime:192 ms, faster than 27.86% of C++ online submissions forLongest Palindromic Substring.
Memory Usage:13 MB, less than 54.45% of C++ online submissions for Longest Palindromic Substring.
毕竟跟前面的暴力遍历没什么区别
