题目描述

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

样例

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

算法1

(暴力枚举) $O(n^2)$

首先，最长回文串包含两种，一种是长度恰好为奇数的，另一种是恰好长度为偶数的。
因此这里需要枚举两种情况。因此我们在这里不妨枚举字符串的中心位置是哪一个位置。
以此达到不重不漏的目的。

1. 当回文串为奇数时，
   定义l = i - 1, r = i + 1,然后找出最左端与最右端,需要注意的是最后一次循环的时候
   s[l] 与 s[r] 不相等(除去他们越界的情况，即使越界的话也不会影响后面的结果表达)
   if(res.size() < r - l - 1) 此时更新答案
   区间为[l+1,r-1]此时区间的长度为 r - 1 - (l - 1) + 1 = r - l - 1
   此时字符串为s.substr(l + 1, r - l - 1)

2. 当回文串为偶数时，左右两个起始的枚举端点为i , i + 1
   之后的处理过程类似于奇数回文串

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for(int i = 0; i < s.size(); i ++){
            int l = i - 1 , r = i + 1;
            while(l>=0 && r < s.size() && 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 < s.size() && s[l] == s[r]) l --, r ++ ;
            if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);        
        }
        return res;
    }
};

更好的阅读体验