LeetCode 5. Longest Palindromic Substring
程序员文章站
2024-03-23 11:44:58
...
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"
题目范围小于1000所以可以用n^2的算法
枚举中心点,用两个指针向两个方向遍历
要分为回文字串长度是奇数和偶数的情况
class Solution {
public:
string longestPalindrome(string s) {
int len = -1;
string ans;
for(int pos = 0; pos < s.size(); ++ pos){
// 回文字串长度为偶数
int i = pos, j = pos + 1;
while(~i && j < s.size() && s[i] == s[j]) i --, j ++;
if(j - i - 1 > len){
len = j - i - 1;
ans = s.substr(i + 1, len);
}
i = pos - 1, j = pos + 1;
while(~i && j < s.size() && s[j] == s[i]) i --, j ++;
if(j - i - 1 > len){
len = j - i - 1;
ans = s.substr(i + 1, len);
}
}
return ans;
}
};
推荐阅读
-
5. Longest Palindromic Substring
-
5. Longest Palindromic Substring
-
LeetCode 5. Longest Palindromic Substring
-
5. Longest Palindromic Substring
-
5. Longest Palindromic Substring
-
LeetCode 5. Longest Palindromic Substring (DP)
-
5. Longest Palindromic Substring
-
Given a string s, find the longest palindromic substring in s. You may assume that the maximum lengt
-
LeetCode[字符串] - #3 Longest Substring Without Repeating Characters 博客分类: LeetCode LeetCodeJavaAlgorithm题解String
-
[LeetCode]3. Longest Substring Without Repeating Characters无重复字符的最长子串