一、题目
提示:
- 1 <= s.length <= 1000
- s 仅由数字和英文字母(大写和/或小写)组成
二、思路
中心扩散法。
从每个节点开始,当前结点向两边扩散来判断回文串,因为回文串长度可能是奇数或者偶数,即后者就木有一个中心字符,伪代码应该如下:
for 0 <= i < len(s): 找到以 s[i] 为中心的回文串 找到以 s[i] 和 s[i+1] 为中心的回文串 更新答案
我们通过传入的左指针l
和右指针r
,可以同时处理回文串为奇数和偶数的情况。注意palindrome
函数最后的s.substr(l+1, r-1-l)
中,右边界是相对下标,其计算是:(r-1)-(l+1)+1=r-l-1
。
三、代码
class Solution { public: string longestPalindrome(string s) { string ans; for(int i = 0; i < s.size(); i++){ //以s[i]为中心的最长回文子串 string s1 = palindrome(s, i, i); //以s[i]和s[i+1]为中心的最长回文子串 string s2 = palindrome(s, i, i + 1); //ans = longest(ans, s1, s2) if(ans.size() < s1.size()){ ans = s1; } if(ans.size() < s2.size()){ ans = s2; } } return ans; } string palindrome(string& s, int l, int r){ //防止索引越界 while(l >= 0 && r < s.size() && s[l] == s[r]){ //向两边展开 l--;r++; } return s.substr(l + 1, r - l - 1); } };