7.21 最长回文子串 【中等】

【题目描述】

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

【主要思路】

回文串（palindromic string）: 是指这个字符串无论从左读还是从右读，所读的顺序都是一样的。即该串是对称的。

① 暴力枚举法

枚举所有长度大于等于2的子串，依次判断他们是否是回文串

暴力枚举法时间复杂度过高，效率太低

②中心扩散法

以数组中的某个元素为中心，向两侧进行扩散，通过不断遍历数组，得到最长的子串。

注意：

扩散中心可能以一个元素为中心或以两个元素为中心，因此在具体实现时，应进行相应的处理。

图片源自LeetCode官方题解

【解题代码】

// 暴力枚举法
class Solution {
public:
    string longestPalindrome(string s) {
        string ret = "";                           // 结果
        string temp = "";                          //                   
        
        // 一力破万法
        // 外层循环 改变起始位置
        // 内层循环 改变终止位置
        for (int i = 0; i < s.length(); i++){
            for (int j = i; j < s.length(); j++){
                temp = temp + s[j];
                // 如果是回文串, 且长度大于等于当前结果, 则替换
                string temp_rev = temp;
                reverse(temp_rev.begin(), temp_rev.end());
                if( temp == temp_rev && temp.length() >= ret.length()){
                    ret = temp;
                }
            }
            // 注意在一次内层循环结束后 要将temp 清空, 下次开始时不会出错
            temp = "";
        }
        
        return ret;
    }
};

// 中心扩散法
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();                                             // 字符串长度
        int start, end = 0;                                             // 记录子串的起始，终止位置，
        int sub_len = 0;                                                // 子串长度
        
        if(len == 0 || len == 1)                                        // 空串 或 只有一个字符
            return s;
        
        // 遍历查找
        for(int i = 0; i < len; i ++){
            // 当中心元素为一个时
            int odd_len = centerSpread(s, i, i);
            // 当中心元素为两个时
            int even_len = centerSpread(s, i, i+1);
            sub_len = max(max(odd_len, even_len), sub_len);             // 最长的子串
            
            // 更新子串的起始，终止位置，便于切片
            if(sub_len > end-start+1){
                start = i - (sub_len-1) / 2;                            // 元素位序与下标之间差1
                end = i + sub_len / 2;
            }
        }
        return s.substr(start, sub_len);
    }
    
    int centerSpread(string s, int left, int right){
        /*
        **      中心元素向两侧扩散
        **  s:          字符串
        **  left:       左侧起始位置
        **  rigt:       右侧终止位置
        */
        while(left >= 0 && s[left]==s[right] && right < s.length()){
            left--;
            right++;
        }
        return right-left-1; 
    }
};

【复杂度分析】

暴力枚举法复杂度为$O(N^3)$O(N3)，在reverse()反转字符串时的复杂度为$O(N)$O(N)，因此整体的复杂度为$O(N^3)$O(N3)。

中心扩散法的复杂度为$O(N^2)$O(N2)

N为字符串长度，每个回文中心向外最多扩展N次。

【参考文章】
最长回文子串c++