Description:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
AC代码:
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() <= 1) return s;
int maxIdx = 0;
int maxLen = 1;
int i = 0;
while (i < s.size()) {
int start = i;
int end = i;
// expand the window from the end if it's an even palindrome
while (end + 1 < s.size() && s[end] == s[end + 1]) { end++; }
i = end + 1;
// expand the window from both sides until it's not longer a palindrome
while (start - 1 >= 0 && end + 1 < s.size() && s[start - 1] == s[end + 1]) {
start--, end++;
}
int currLen = end - start + 1;
if (currLen > maxLen) {
maxIdx = start;
maxLen = currLen;
}
}
return s.substr(maxIdx, maxLen);
}
};
测试与结果
int main() {
Solution s;
string testString1 = "ababa";
string result1 = s.longestPalindrome(testString1);
cout << result1 << endl;
string testString2 = "cbbd";
string result2 = s.longestPalindrome(testString2);
cout << result2 << endl;
}
总结
本题将窗口按照两个方向进行扩展，如果遇到重复字符，就按照end++的方向扩展，直至不重复为止。如果不存在重复字符，就尝试从两个方向扩展窗口，直至不满足回文的条件为止。
