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%的用戶