runtime 13 ms, beats 94.30% of cpp submissions
O(n^2) solution with explanation

tags: palindrome

Longest Palindromic Substring

🧷 extended

Manacher’s Algorithm

📖 description

給定一個字串 s ，找出最長的回文子字串
ex. babad -> bab , aba 都是最長的回文子字串

🧠 solution

本題可以藉由 Manacher’s Algorithm (馬拉車演算法) 來進一步降低時間複雜度到 O(n) ，但目前仍在理解中。

最基礎的想法是找出所有的子字串，並一一測試他是否回文，但找出所有子字串的時間複雜度為 O(n^3) ，而其實在這個部分可以利用回文字串的特性做出化簡，使用中心擴散的方法來降低時間複雜度。

以 s = baabad 為例，可以挑每個字元當作擴散的起點，來找到符合的子字串
此時會有兩種狀況

  • 要找的回文子字串是奇數的，比如以 baabad 的第2個 b 作為中心找到 aba
  • 要找的回文子字串是偶數的，比如以 baabad 的第1個與第2個 a 作為中心找到 baab

當跑過所有的 index 時就會找到最長的回文子字串了

⏳ time complexity

遍歷字串 O(n) ，最糟狀況下每次擴散都會走到某一邊的結尾 O(n) (每次都會走到最小段的結尾)
總時間複雜度 O(n^2)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string longestPalindrome(string& s) {
        int max_left = 0;                           // 當前最長回文子字串的開頭
        int max_len = -1;                           // 當前最長回文子字串的長度
        bool isodd = false;                         // 兩種擴散方式不一樣
        for(int i=0;i<s.size();i++){
            int odd = expand(s,i,i);                // 奇數由特定點進行擴散
            int even = expand(s,i,i+1);             // 偶數由兩點開始進行擴散
            if(max_len<odd || max_len<even){        // 維護最長回文子字串
                max_left=i;
                max_len = max(odd,even);
                isodd = odd>even ? true : false;
            }
        }
        if(isodd){
            return s.substr(max_left-max_len/2,max_len);
        }
        else{
            return s.substr(max_left-max_len/2+1,max_len);
        }
    }
    int expand(string& s,int l,int r){
        while(l>=0 && r<=s.size() && s[l]==s[r]){   // 設定邊界，且保證回文的性質
            r++;
            l--;
        }
        r--;
        l++;
        return r-l+1;
    }
};