原题链接

https://leetcode.cn/problems/longest-palindromic-substring/description/

基本思路

指针遍历字符串，每个位置向两侧扩散检查两侧字符是否相等。遍历时间复杂度O(n)，扩散时间复杂度O(n)，总时间复杂度O(n^2)，总空间复杂度O(1)。

特殊情况：回文串中心可能落在两个元素中间，即"baab"的回文中心在两个a中间。

我选择开俩指针，j是遍历指针，i是j的prev

代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty() || s.size() == 1) return s;  // 双指针避免下标越界，先把空字符串和单元素字符串干掉
        int i = 0, j = 1;  // 单元素默认为回文串，从第2个元素开始遍历
        int res = 1;  // 存目前记录的最长回文串长度
        int resl = 0, resr = 0;  // 存最长回文串的左右端下标
        while (j < s.size()) {  // 遍历条件
            // 1. j为回文中心
            int curr = 1;  // 当前检查的回文串长度，默认单元素s[j]为回文串
            int l = i, r = j + 1;  // 待检查的回文串左右端下标
            while (l >= 0 && r < s.size()) {  // 检查回文串合法性前，检查数组下标是否越界
                if (s[l] == s[r]) {  // 如果是回文串
                    curr += 2;
                    if (curr > res) {  // 如果当前回文串是最长回文串
                        res = curr;
                        resl = l, resr = r;
                    }
                    l--, r++;  // 继续扩散
                }
                else break;  // 如果不是回文串则不再继续检查
            }
            // 2. i与j为中心
            curr = 0;  // 尚不知s[i], s[j]是否能组成回文串
            l = i, r = j;
            while (l >= 0 && r < s.size()) {
                if (s[l] == s[r]) {
                    curr += 2;
                    if (curr > res) {
                        res = curr;
                        resl = l, resr = r;
                    }
                    l--, r++;
                }
                else break;
            }
            i++, j++;  // 继续遍历下一个位置
        }
        return s.substr(resl, resr - resl + 1);
    }
};