LeetCode: 5-Longest Palindromic Substring 解題紀錄

Last Updated on 2021-01-03 by Clay

題目

Given a string s, return the longest palindromic substring in s.

Example:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

題目給定一個輸入字串，而我們要在這個字串中，找到最大的『回文子字串』。回文（palindromic）是什麼意思呢？就是即使字串顛倒過來也是相同的，就好比範例中的 bab 一樣，顛倒過來同樣是 bab。

不過這題要求回傳的答案只要是任一最長的回文子字串即可，不需要回傳『全部』的答案，也算是某種程度的佛心來著？（雖說只要將最長的都記錄起來就行了）

解題思路

方法一：滑動窗口（失敗？）

一開始我使用滑動窗口（sliding window）來解題，從大長度一直降到只剩唯一字元，只要找到一解就提早結束，回傳答案。（畢竟是從最長的窗口尺寸開始搜尋）

這個方法很神奇地，有時 TLE（Time Limit Exceeded）有時又不會 …… 所以我開始思考另外的解題方法。

方法二：字中心擴展（失敗）

這是我嘗試的第二個解題方法，很可惜只有在 test case 成功，實際提交時一定會 TLE。

簡單來說就是我考慮以一個字元為中心，然後去看這個字元左右字元是否相同，如果相同，就記錄起來，然後繼續看左右字元更外面的左右字元 …… 直到最左端和最右端不同為止，我才開始往以下一個字元為中心計算。

不過在以『一個字元為中心』後，需要再跑一次，這次以『兩個同樣字元』為中心的方法去擴展，原因很簡單，因為回文子字串也可能是 abba 這樣的形式。

雖然我怎麼跑都失敗，不過上網一查後發現有人同樣也用這種方法，而且還是成功的 …… 或許有我沒想通的地方。

方法三：動態規劃（DP）

我是在寫這篇紀錄文章時，苦惱於我的第一個方法效率太差，究竟要不要分享的時候才看到這種解法的，哈哈。只能說，有時候一個題目可能有很多種解法，但是人們會陷入盲點。

其實不論是我的第一個或是第二個方法，其中都會有太多重複計算的字元比對，所以，這個題目使用 DP 可能算是很恰當又很直覺的方法。（不過當我寫完之後效率卻沒有過半）

（不過，不要太在乎 LeetCode 的分數！）
（能過就好！）

以上面的範例 babad 為例，首先我們要建立個 DP 表，並將表格全部初始化為 False。

若其中一格為 True，比方說 dp[0][2] 為 True，則代表從 0 到 2 的字串 bab 為回文。而我們要做的，就是完善這張 DP 表。

首先，單一字元肯定是相同的，所以 DP 表的對角線要全部填上 True。

然後我們開始真正完善此一表格，首先建立雙重迴圈，讓 i 從 3 開始遞減，而每一次都讓 j 從 i+1 遞增到最大長度為止。然後在完善 DP 表的同時，最重要的就是判斷 s[i] 和 s[j] 是否相同。

s[i] 和 s[j] 相同的情況下：

• 若 j 和 i 相差為 1 或是 dp[i+1][j-1] 為 True，則 dp[i][j] 為 True
• dp[i][j] 為 True，若 max_sub_str 長度小於 j – i + 1，則更新 max_sub_str

Step 1: i=3, j=4 –> a 和 b 不相同

Step 2: i=2, j=3 –> b 和 a 不相同
Step 3: i=2, j=4 –> b 和 d 不相同
Step 4: i=1, j=2 –> a 和 b 不相同

Step 5: i=1, j=3 –> a 和 a 相同且 dp[i+1][j-1]（dp[2][2]）

==> dp[1][3] 為 True，更新 max_sub_str。

Step 6: i=1, j=4 –> a 和 d 不相同
Step 7: i=0, j=1 –> b 和 a 不相同
Step 8: i=0, j=2 –> b 和 b 相同且 dp[i+1][j-1]（dp[1][1]）

…… 依此類推，最終我們會完成我們的 DP 表，同時也有最長的回文子字串了。簡單來講，這是一種使用記憶體換取速度的解題方法。

以下是我實作的程式碼。

C++ 程式碼

class Solution {
public:    
    string longestPalindrome(string s) {
        // Preventation
        if (s.size() <= 1) {
            return s;
        }
        
        // Init
        int n = s.size();
        bool dp[n][n];
        memset(dp, false, sizeof(dp));
        string max_sub_str;
        max_sub_str += s[0];
        
        // Diagonal
        for (int i=0; i<n; i++) dp[i][i] = true;
        
        // Complete the DP table
        for (int i=n-2; i>=0; i--) {
            for (int j=i+1; j<n; j++) {
                if (s[i] == s[j]) {
                    if (j-i == 1 or dp[i+1][j-1] == true) {
                        dp[i][j] = true;
                        if (max_sub_str.size() < j-i+1) {
                            max_sub_str = s.substr(i, j-i+1);
                        }
                    }
                }
            }
        }
        
        return max_sub_str;
    }
};

Python 程式碼

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Preventation
        if len(s) <= 1: return s
        
        # Init
        dp = [[False]*len(s) for _ in range(len(s))]
        for i in range(len(s)): dp[i][i] = True
        
        max_sub_str = s[0]
        
        # Complete the DP table
        for i in range(len(s)-2, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    if j-i==1 or dp[i+1][j-1] == True:
                        dp[i][j] = True
                        
                        if len(max_sub_str) < j-i+1:
                            max_sub_str = s[i:j+1]
        
        return max_sub_str

不過目前我試過的三種方法都沒有過 50% 人的速度 …… 究竟該怎麼樣才能進一步提速呢？

References

• https://leetcode.com/problems/longest-palindromic-substring
• Clay-Technology World: LeetCode 解題紀錄目錄