5. Longest Palindromic Substring

📘 題目敘述

給定一個字串 s，請找出 s 中最長的迴文子字串（palindromic substring）。

迴文字串指的是：從左往右讀與從右往左讀完全相同的字串。

條件限制

• 1 ≤ s.length ≤ 1000
• s 只包含英文字母與數字

🧠 解題思路 (一) 直覺想法

我把這題想成「找迴文的中心，然後往外擴張」的過程。

因為迴文一定是左右對稱，所以只要先確定中心位置，就能往外一層一層比對。

我的做法分成三大步：

1. 先處理字串長度很小的邊界情況（長度 1 或 2）
2. 接著先找「偶數長度」迴文（中心在兩個字中間）
3. 再找「奇數長度」迴文（中心在某一個字上）

這樣做的原因是：迴文的中心型態只有兩種（偶數中心 / 奇數中心），把它們分開處理會比較直覺。

所有變數

• best：目前找到的最長迴文子字串，一開始先設為第一個字元
• now：在某個中心展開時，目前正在形成的迴文子字串（暫存用）

步驟一：先處理長度 1 或 2 的情況

• 若 s.size() == 1：答案就是整個字串本身
• 若 s.size() == 2：
  • 若兩個字相同，整個字串就是迴文，回傳 s
  • 否則最長迴文只能是任意一個單字元，回傳 best

這樣做是為了避免後面展開時遇到不必要的邊界麻煩，也讓邏輯更乾淨。

步驟二：處理「偶數長度」迴文（中心在 i 和 i+1 之間）

偶數長度迴文的特徵是：中間會有兩個相同的字元，例如 "bb"。

因此我先枚舉每一個可能的中心 (i, i+1)：

• 只有當 s[i] == s[i+1] 時，才有可能形成偶數迴文
• 一旦確認中心成立，就從這個中心向外擴張，比較左右兩邊是否仍相等
• 若左右仍相等，就把迴文擴大；一旦不相等就停止

步驟三：處理「奇數長度」迴文（中心在 i+1）

奇數長度迴文的特徵是：中間會有一個中心字元，例如 "aba" 的中心是 'b'。

我的寫法是把中心視為 (i, i+2) 這種「左右對稱的兩個點」：

• 只有當 s[i] == s[i+2] 時，才表示以 i+1 為中心至少能形成長度 3 的迴文
• 一旦確認中心成立，就同樣向外擴張，比較更外層的左右字元是否相等
• 若左右仍相等就繼續擴大；不相等就停止

每次擴充字串後要做什麼？

不論是偶數中心或奇數中心，只要我目前形成的迴文 now 長度超過 best，就立刻更新：

• best = now

最後回傳 best，就是全域最長的迴文子字串。

💻 程式碼實作

class Solution {
public:
    string longestPalindrome(string s) {
        string best = s.substr(0, 1);
        if (s.size() == 1) {
            return best;
        }
        if (s.size() == 2) {
            if (s[0] == s[1]) {
                return s;
            } else {
                return best;
            }
        }
        for (int i = 0; i < s.size() - 1; i++) {
            if (s[i] == s[(i + 1)]) {
                string now = "";
                for (int j = i; (j >= 0) && (2 * i + 1 - j < s.size()); j--) {
                    if (s[j] == s[2 * i + 1 - j]) {
                        now = s[j] + now;
                        now.push_back(s[2 * i + 1 - j]);
                    } else {
                        break;
                    }
                    if (now.size() > best.size()) {
                        best = now;
                    }
                }
            }
        }
        for (int i = 0; i < s.size() - 2; i++) {
            if (s[i] == s[(i + 2)]) {
                string now = s.substr(i + 1, 1);
                for (int j = i; (j >= 0) && (2 * i + 2 - j < s.size()); j--) {
                    if (s[j] == s[2 * i + 2 - j]) {
                        now = s[j] + now;
                        now.push_back(s[2 * i + 2 - j]);
                    } else {
                        break;
                    }
                    if (now.size() > best.size()) {
                        best = now;
                    }
                }
            }
        }
        return best;
    }
};

🧠 解題思路（二）：DP（動態規劃）

參考了一下官方提供解法，利用 Dynamic programming 解題。

先用一個表格記錄「某一段子字串是不是迴文」，之後就能用更小的區間推導更大的區間。

DP 的想法

我建立一個二維 bool 陣列 dp：

• dp[i][j] = true 表示 s[i..j]（從 i 到 j 的子字串）是迴文
• dp[i][j] = false 表示不是迴文

核心轉移關係是：

• 如果 s[i] == s[j]，且內層的子字串 s[i+1..j-1] 是迴文，那麼 s[i..j] 也是迴文

也就是：

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

所有變數

• start：目前最長迴文的起點
• len：目前最長迴文的長度

最後回傳 s.substr(start, len)。

初始化（先處理長度 1 與 2）

因為 DP 需要從小區間開始建立：

長度 1

任何單一字元一定是迴文：

• dp[i][i] = true

長度 2

• 若 s[j] == s[j+1]，則 dp[j][j+1] = true
• 同時更新 start = j、len = 2

狀態轉移（長度 ≥ 3）

接著我用 k 表示子字串長度（從 3 一路做到 n）：

• 枚舉起點 l
• 終點就是 r = l + k - 1
• 只要：
  • s[l] == s[r]（首尾相同）
  • dp[l+1][r-1] == true（中間那段也是迴文）
• 就能推出 dp[l][r] = true

並且每次找到更長的迴文，就更新：

• start = l
• len = k

最後回傳

• 回傳 s.substr(start, len)，就是最長迴文子字串

💻 程式碼實作（DP 版本）

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        int start = 0;
        int len = 1;
        if (n <= 1) {
            return s;
        }
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        // dp[i][j]：看 s[i] 到 s[j] 是否為迴文

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        for (int j = 0; j < n - 1; j++) {
            if (s[j] == s[j + 1]) {
                dp[j][j + 1] = true;
                start = j;
                len = 2;
            }
        }
        for (int k = 3; k <= n; k++) {
            for (int l = 0; l < n - k + 1; l++) {
                if ((s[l] == s[l + k - 1]) && dp[l + 1][l + k - 2]) {
                    dp[l][l + k - 1] = true;
                    start = l;
                    len = k;
                }
            }
        }
        return s.substr(start, len);
    }
};

🔗 題目連結

https://leetcode.com/problems/longest-palindromic-substring/