LeetCode-5.最長回文子串 中心擴散法

暴力法：擷取所有字元串組合，并判斷是否回文，時間複雜度達到了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%的使用者