题目描述
给你一个字符串 s,找到 s 中最长的回文子串。
样例
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
算法1
(暴力枚举) $O(n^2)$
字符串长度为1000,可以采取暴力枚举的方式。
从头至尾枚举回文串中心点i(0-n-1)然后分成两种情况:
1. 回文串长度为奇数,中心点i满足要求,令l = i -1, r = i + 1,向两边扩展满足s[l] == s[r]就一直向外走,直到不满足条件
2. 回文串长度为偶数,令l = i, r = i + 1向两边扩展,如上
3. 每次l和r停下来就记录当前最长的回文串
时间复杂度
双重循环
C++ 代码
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
string res;
for(int i = 0; i < n; i++){
int l = i - 1, r = i + 1;
while(l >= 0 && r < n && s[l] == s[r]) l--, r++;
if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
l = i, r = i + 1;
while(l >= 0 && r < n && s[l] == s[r]) l--, r++;
if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
}
return res;
}
};
算法2
(动态规划) $O(n^2)$
C++ 代码
blablabla