647. Palindromic Substrings

題目網址：https://leetcode.cn/problems/palindromic-substrings/

題意：給一 string s, 返回迴文 substring 數量。

Solution 1：

想法：利用DP, 可參考 5. Longest Palindromic Substring

class Solution {
public:
    int countSubstrings(string s) {
        const int n = s.size();
        int res = n; // 每個 char 自己本身(對角線)為回文
        vector<vector<bool>> dp(n, vector<bool>(n, true));

        for (int j = 1; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];

                if (dp[i][j]) {
                    ++res;
                }
            }
        }
        return res;
    }
};

• time：$O(n^2)$ ➔ for loop
• space：$O(n^2)$ ➔ dp

Solution 2：

想法：利用中心擴散法

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        const int n = s.size();
        for (int i = 0; i < n; ++i) {
            expand(s, i, i, n, res); // odd string
            expand(s, i, i + 1, n, res); // even string
        }
        return res;
    }

private:
    void expand(const string& s, int left, int right, const int n, int& res){
        while (left >= 0 && right < n && s[left] == s[right]) {
            --left;
            ++right;
            ++res;
        }
    }
};

• time：$O(n^2)$ ➔ 遍歷每個 char, 每個 char 為中心最多往外擴散 $\dfrac{n}{2}$ 次, 得 $2 \cdot O(\dfrac{n}{2}) \cdot n$
• space：$O(1)$ ➔ 只需常數空間

Solution 3：（不會也沒差, 會前兩種方法就足夠了）

想法：利用 Manacher 演算法, 可參考 5. Longest Palindromic Substring, res += (p[i] + 1) / 2 的原因為以下兩種：

• 若 p[i] = 1："abc" 擴充後 a, b, c 之 p[i] 皆為 1, 擴充半徑為 1, 代表回文只有自己, 但這也算一種回文
• 若 p[i] > 1："aba" 擴充後 b 之 p[i] = 3, 從 b 為中心得到的回文 substring 有："b"（擴充半徑 = 0）和 "aba"（擴充半徑 = 1）, 也就是擴充半徑 [0, (p[i] / 2)], 共 (p[i] / 2) + 1 種, 也可寫作 (p[i] + 1) / 2 種（奇偶都符合）

➔ 公式：(p[i] + 1) / 2 滿足上述兩種情況

class Solution {
public:
    int countSubstrings(string s) {
        string tmp = preProcess(s);
        const int n = tmp.size();
        vector<int> p(n - 1, 0); // 最後一個 $ 不用算
        int right = 0, center = 0, res = 0;

        for (int i = 1; i < n - 1; ++i) {
            const int idxMirror = 2 * center - i;

            // 防止超出 right
            if (i < right) {
                p[i] = min(p[idxMirror], right - i);
            } else { // i >= right 的時候
                p[i] = 0; 
            }

            /*
             * 有三種情況, 需使用中心擴散法
             * 1. i + p[idxMirror] > right
             * 2. i >= right 的時候
             * 3. p[idxMirror] 遇到左邊界
             */
            while (tmp.at(i - 1 - p[i]) == tmp.at(i + 1 + p[i])) {
                ++p[i];
            }

            // 判斷是否超出右邊界, 是的話要更新右邊界和中心
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            res += (p[i] + 1) / 2;
        }
        
        return res;
    }

private:
    string preProcess(const string& s){
        string tmp = "^";
        for (int i = 0; i < s.size(); ++i) {
            tmp += "#";
            tmp += s[i];
        }
        tmp += "#$";
        return tmp;
    }
};

• time：$O(n)$ ➔ 透過不斷拓展 right, 且 right 只增不減, 故只看 for loop, 因為 while loop 拜訪過的 char 不會再進 while loop（可透過 DP 快速得到）
• space：$O(n)$ ➔ tmp, p 的長度 = 2 * s.size() + 3