1.题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

示例 3：
输入：s = “a”
输出：“a”

示例 4：
输入：s = “ac”
输出：“a”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

其实刚开始我很不理解，自己写了一个暴力破解。

string longestPalindrome(string s) {
    
    string ans = "";
    ans += s[0];
    int n = s.size();
    for(int i = 0;i < n;i++){
    
        for(int j = i + 1;j < n;j++) {
    
            string s1 = s.substr(i,j - i + 1);
            string s2 = s1;
            reverse(s2.begin(),s2.end());
            if(s1 == s2) {
    
                ans = s1.size() > ans.size() ? s1 : ans;
            }
        }
    }
    
    return ans;
}

超时了。
去看别人的题解，看到了一个双指针。

2.1.比较好理解的双指针

看了那么多的题解，感觉还是这个双指针比较好理解，
对于这题的双指针，就是以某个点（或者）为中心，向左右两边同时扩散，判断是否构成回文。

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
s[i]	a	b	a	d	a	b	a	a	b	a	a	c	d	b	d

对于上表，当枚举到s[1] (b)时，取i = 1,j = 1;i–,j++的同时，判断s[i]是否等于s[j]，相等则继续往两边判断，否则停止判断。
当然，会有abba这种情况的回文，所以我们不能只以一个字符为中心，还要有两个字符为中心的，所以判断完上一个之后，要取i = 1,i = 1 + 1即（left = i, right = i + 1），进行判断，
然后分别计算两种情况下得到的回文长度，在第一种情况回文长度、第二种回文长度中和当前的回文长度中取最大值，要更新起始位置。

（1）以一个点为中心，向两边同时扩展，判断是否构成回文。
（2）以两个点为中心，向两边同时扩展，判断是否构成回文。

2.2.代码

这个代码虽然长，但是它不会涉及函数调用，函数调用涉及很多出栈和入栈，消耗空间和时间，所以这样写反而节省时间和空间。

string longestPalindrome(string s) {
    
    int left = 0;
    int maxlen = 1;
    int n = s.size();
    for(int i = 0;i < n;i++){
    
        //一个中心
        int l = i;
        int r = i;
        bool in = false;
        while(l>=0&&r<n&&s[l]==s[r]) {
    
            l--;
            r++;
            in = true;
        }
        
        if(in && (r - l - 1) > maxlen){
    
            maxlen = r-l-1;
            left = l + 1;
        }
        
        //两个中心
        l = i;
        r = i+1;
        in = false;
        while(l>=0&&r<n&&s[l]==s[r]) {
    
            l--;
            r++;
            in = true;
        }
        if(in && (r - l - 1) > maxlen){
    
            maxlen = r-l-1;
            left = l + 1;
        }
    }
    
    return s.substr(left,maxlen);
}

结果

2.3.加函数代码

可以看到有两段代码一样，改进（但是时间空间没有优化）

string longestPalindrome(string s) {
    
    int left = 0;
    int maxlen = 1;
    int n = s.size();
    for(int i = 0;i < n;i++) {
    
        expand(s, i, i, n, left, maxlen);//一个中心
        expand(s, i, i + 1, n, left, maxlen);//两个中心
    }
    return s.substr(left, maxlen);
}

void expand(string s, int l, int r, int n, int& left, int& maxlen) {
    
    bool in = (l >= 0 && r < n && s[l] == s[r]);
    while(l >= 0 && r < n && s[l] == s[r]) {
    
        l--;
        r++;
    }

    if(in && (r - l - 1) > maxlen) {
    
        maxlen = r - l - 1;
        left = l + 1;
    }
}

结果

3.结语

想尽办法减少时间和空间的利用。