LeetCode-5.最长回文子串 中心扩散法

题目

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

示例 1：

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

暴力法：获取所有字符串组合，并判断是否回文，时间复杂度达到了O(n³)

中心扩散法：时间复杂度O(n²)，且十分简单。总体思想为遍历一遍字符串，对每个字符进行左右扩散来判断是否存在回文，并记录最长回文长度。

下面展示C++实现中心扩散法的代码

#include <iostream>
#include <string>
using namespace std;

/**
 * LeetCode
 * 5. 最长回文子串
 * https://leetcode-cn.com/u/banana798/
 */

class Solution {
public:
    string longestPalindrome(string s) {
        int strLen = s.size();
        if(s.empty() || strLen==0){
            return "";
        }
        if(s.size()==1){    //这里进行了小优化
            return s;
        }
        //maxLen为最长回文长度,maxStart为最长回文时起始位置
        int left=0,right=0,len=1,maxLen=0,maxStart=0;

        //对每个字符进行左右扩散
        for(int i=0; i<strLen; i++){
            left = i-1;
            right = i+1;

            while(left>=0 && s[left]==s[i]){
                left--;
                len++;
            }

            while(right<strLen && s[right]==s[i]){
                right++;
                len++;
            }

            while(left>=0 && right<strLen && s[left]==s[right]){
                left--;
                right++;
                len+=2;
            }

            if(len > maxLen){
                maxLen = len;
                maxStart = left<0?-1:left; //返回-1是因为下面maxStart+1
            }
            len = 1;    //恢复len=1
        }
        //返回从maxStart+1下表开始，长度为maxLen的字符串
        return s.substr(maxStart+1, maxLen);
    }
};

int main(){
    Solution solution;
    cout << solution.longestPalindrome("abcbaba");
}

运行结果：通过

执行用时：88 ms, 在所有 C++ 提交中击败了69.52%的用户

内存消耗：6.6 MB, 在所有 C++ 提交中击败了100.00%的用户

文章永久链接：https://tech.souyunku.com/27324