LeetCode 解題筆記：5. Longest Palindromic Substring

作者：王一哲
日期：2026年7月17日


LeetCode 題目連結：5. Longest Palindromic Substring

解題想法

中等難度題。題目給一個字串 $s$，要找出 $s$ 之中最長迴文子字串長度。這題我是用暴力解，先在 $s$ 兩端加上不可能出現的字元當作邊界，再分成奇數長度、偶數長度的子字串各處理一次。用一個 for 迴圈列舉所有可能的中心點索引值，如果是奇數長度中心點為 $c = 1$ 到 $c = len(s) - 2$，如果是偶數長度中心點為 $c = 1$ 到 $c = len(s) - 3$；再用一個 while 迴圈由 $c$ 向兩側延伸，如果兩側的字元相同，可以組長更長的迴文子字串，繼續向外延伸；當 while 迴圈結束時，更新答案。速度比想像中快很多。

Python 程式碼

Runtime: 155 ms, beats 96.12%. Memory: 19.18 MB, beats 91.25%.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = '[' + s + ']'  # 兩端加上不可能出現的字元當作邊界
        # 處理奇數長度的字串，c 為中心點，r 為位移量值，檢查範圍為 s[c-r] ~ s[c+r]
        longest = ""  # 最長字串，預設為空字串
        for c in range(1, len(s)-1):  # 依序檢查 c = 1 ~ len(s)-2，要扣掉另外加上去的 []
            r = 1
            while s[c-r] == s[c+r]: r += 1  # 結束時 r 多加 1，回文字串長度為 2*(r-1)+1 = 2*r -1
            if r+r-1 > len(longest):  # 如果新找到的回文字串較長
                longest = s[c-r+1:c+r]
        # 處理偶數長度的字串，i 為中心點，r 為位移量值，檢查範圍為 s[i-r] ~ s[i+r+1]
        for i in range(1, len(s)-2):  # 依序檢查 i = 1 ~ len(s)-3，要扣掉另外加上去的 []
            r = 0
            while s[i-r] == s[i+r+1]: r += 1  # 結束時回文字串長度為 2*r
            if r+r > len(longest):
                longest = s[i-r+1:i+r+1]
        return longest

C++ 程式碼

Runtime: 3 ms, beats 98.15%. Memory: 12.39 MB, beats 45.84%.

class Solution {
public:
    string longestPalindrome(string s) {
        s = "[" + s + "]";
        string longest = "";
        size_t r;
        for(size_t c=1; c<s.size()-1; c++) {
            r = 1;
            while(s[c-r] == s[c+r]) r++;
            if (r+r-1 > longest.size()) longest = s.substr(c-r+1, r+r-1);
        }
        for(size_t i=1; i<s.size()-2; i++) {
            r = 0;
            while(s[i-r] == s[i+r+1]) r++;
            if (r+r > longest.size()) longest = s.substr(i-r+1, r+r);
        }
        return longest;
    }
};