题目描述
来源:Longest Palindromic Substring
给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
算法分析
直接模拟+双指针法
题目分析
首先,根据题目条件,回文串的特点是:
从中心向两边发散的过程中字符相等
算法思路
结合回文串的特点,不难想出用两个指针模拟从中心向两边发散的过程,利用一个变量记录中心的位置,根据左右指针之间的长度更新答案
需要注意
- 何时停止双指针中心发散过程:
当两个指针对应的字符不同时 - 何时开始双指针中心发散过程
当两个指针对应的字符相同时 - 由于while循环语句的特点,右指针right对应的字符为回文串末尾的下一个位置,左指针left对应的字符为回文串开头的前一个位置,因此回文串实际长度为right-1-(left+1)+1
时间复杂度:O(n^2)满足1 <= s.length <= 1000
的条件
代码实现
class Solution {
public:
string longestPalindrome(string s) {
if(s.empty()) return s;
string result;
int n = s.size();
for(int i = 0; i < n; i ++) {
int left = i - 1, right = i + 1;
while(left >= 0 && right < n && s[left] == s[right]) left --, right ++;
//如上分析,回文串长度为right-1-(left+1)+1=right-left-1
if(result.size() < right - left - 1) result = s.substr(left + 1, right - left - 1);
left = i, right = i + 1;
while(left >= 0 && right < n && s[left] == s[right]) left --, right ++;
if(result.size() < right - left - 1) result = s.substr(left + 1, right - left - 1);
}
return result;
}
};
总结
- 抓住回文串的性质思考算法思路
- 注意双指针移动和结束时机,以及while循环的特点