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

題意：給一 string s, 找出 s 中最長的迴文 substring。

注意：

  • substring 指的是 string 中 連續的 subset
  • subsequence 則是 string 的 subset

Solution 1：

想法：利用 DP, 因為我們發現「一個迴文去掉兩頭後, 剩下的部分仍為迴文」, 我們用 dp[i][j] 代表 substring s[i~j] 是否迴文, 則可得到下列公式：

  • dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]

dp[i + 1][j - 1] 在 dp[i][j] 的左下方, 故順序為由左至右, 一行一行的填, 其中對角線為 true

e.g. "abba" 中已知 "bb" 為迴文, 所以 dp[1][2] = true

➔ 則 dp[0][3] 則因為 "a" == "a" 且 dp[1][2] = true, 故 dp[0][3] = true, 代表 "abba" 為迴文

class Solution {
public:
    string longestPalindrome(string s) {
        // 當長度為 2 時, e.g. "ac", dp[0][1] = false, 但 "a" 為回文, 故 maxLen 設 1
        int start = 0, maxLen = 1;
        const int n = s.size();
        vector<vector<bool>> dp(n, vector<bool> (n, true)); // 對角線以下皆為 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] && j - i + 1 > maxLen) {
                    start = i;
                    maxLen = j - i + 1;
                }
            }
        }
        return s.substr(start, maxLen);
    }
};
  • time：$O(n^2)$ ➔ for loop：$1+2+…+(n-1) = \dfrac{n(n-1)}{2}$ $= O(n^2)$
  • space：$O(n^2)$ ➔ dp

Solution 2：

想法：利用中心擴散法, 也就是枚舉所有 substring 的中心位置, 總共枚舉 2n 個 substring, 因為每個位置 i 皆要考慮以其為中心的偶數 substring 和奇數 substring

更新 start 時, 之所以為 start = i - (maxLen - 1) / 2, 是因為我們的 i 是左中點, 而非右中點, 故 maxLen 要先減一再除 2

expand(s, left, right, n) 跳出迴圈時, 有兩種可能：

  • s[left] != s[right]：代表 s 中的 [left + 1, right - 1] 區間是回文 substring, 此時的回文substring 長度為 (right - 1) - (left + 1) - 1 = right - left - 1

  • 第二種狀況是 left 或 right 越界, e.g. left = -1 且 right = n, 此時代表整個 s 為回文, 故回文長度為 n
    ➔ 第一種狀況得到的公式 right - left - 1 = n - (-1) - 1 = n 仍然滿足第二種狀況

class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0, maxLen = 1;
        const int n = s.size();

        for (int i = 0; i < n; ++i) {
            const int curLen = max(expand(s, i, i, n), // odd substring
                                   expand(s, i, i + 1, n)); // even substring
            if (curLen > maxLen) {
                maxLen = curLen;
                start = i - (maxLen - 1) / 2; // i 是中心, 要倒推回起點
            }
        }
        return s.substr(start, maxLen);
    }

private:
    int expand(const string& s, int left, int right, const int n){
        while (left >= 0 && right < n && s[left] == s[right]) {
            --left;
            ++right;
        }
        /*
         * 跳出 loop 時, 第一種狀況是 s[left] != s[right]
         * 代表 s[(left+1)~(right-1)] 是回文substring
         * 此時 substring 長度為 (right-1) - (left+1) + 1 = right - left - 1
         * 第二種狀況是越界, left = -1 且 right = n
         * 此時代表整個 string 為回文, 故回文長度為 n
         * 第一種狀況得到的公式 right - left - 1 = n - (-1) - 1 = n 仍然滿足第二種狀況
         */
        return right - left - 1;
    }
};
  • time：$O(n^2)$ ➔ 遍歷每個 char, 每個 char 為中心最多往外擴散 $\dfrac{n}{2}$ 次, 得 $2 \cdot O(\dfrac{n}{2}) \cdot n$
  • space：$O(1)$ ➔ 只需常數空間

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

想法：利用 Manacher 演算法（可參考這篇）, 其核心思想是結合 DP（回文特性）+ 中心擴散

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

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

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

            /*
             * 有三種情況, 需使用中心擴散法
             * 1. i + p[i_mirror] > right
             * 2. i >= right 的時候
             * 3. p[i_mirror] 遇到左邊界
             */
            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];
            }
        }

        // 找出 p 的最大值
        int maxLen = 0, centerIndex = 0;
        for (int i = 1; i < n - 1; ++i) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                centerIndex = i;
            }
        }

        const int start = (centerIndex - maxLen) / 2;

        return s.substr(start, maxLen);
    }

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