Leetcode #647 Palindromic Substrings – 陪你刷題

本篇探討的是 Leetcode #647 Palindromic Substrings 。

理解題意

s = “abc” ，答案為 3 ，分別是各個單一字元形成的回文 string ，由此可知，一個 string 內還基本回文 string 至少為 string 長度。

s = “aaa” ，答案為 6 ，除了 string 本身長度 3 以外，還有 “aa”, “aa” 和 “aaa” 。

討論 input/output 格式

input 為 string ，且都為小寫字母，長度為 1~1000 。

output 為 integer ，要回傳總共有多少個回文 string 。

解釋想法，從暴力解開始

總共有 N^2 種 substring，每個 substring 又需要檢查整個 string （N），因此 time complexity 會到約 O (N^3) 的程度。

優化

這個問題問說存在多少個回文 string ，直覺可以用動態規劃來解。動態規劃問題要符合三個特徵，分別是最佳子結構、重複子問題跟無後效性。

最佳子結構

先看最佳子結構，一個問題的最佳解包含子問題的最佳解嗎？

S = “abqba” 是否為回文 string ，這個問題包含了子問題 “bqb” 是否是回文 string 。

“bqb” 是否為回文 string 這個問題，又包含子問題 “q” 是否為回文 string 這個子問題。

由此可證明，這個問題具有最佳子結構的特性。

重複子問題

再來驗證重複子問題特徵，再以 “abqba” 為例，檢查 “abqba” 和 “bqb” 是否為回文字串時，都需要檢查子問題 “q” 是否為回文子串，至此也證明了重複子問題特徵。

無後效性

無後效性代表當子問題最佳解確定下來後，就不再改變。這個蠻直覺的，原始 string 也不會被更改，子問題的解彼此並不影響。

動態規劃

Step 1

動態規劃第一步來定義”狀態”變數，定義 dp[i][j] 來代表從 index i 到 j 所形成的子字串是否為回文子字串，最終答案也等於 dp 這個二維陣列有多少個元素為 true 。

Step 2 找出遞迴關係式

dp[i][j] = true if

dp[i+1][j-1] is true
S[i] == S[j]

Step 3 定義 base case

dp[i][i] 肯定為 true ， substring 只有單一字元時視為回文。

還有一種 base case 是比較難想到的，那就是只包含兩個 letter 的 substring ，這樣的 substring 不包含任何子問題，因此也算是 base case 的一種。

有了以上定義接下來要填表，要依照什麼順序來填表也是一個困難點，

我們應該這麼想，從 base case 出發來填表， base case 包含所有長度為 1 和 2 的 substring ，接著從長度為 3 的 substring 依序增加 string 長度來填表，直到將所有可能長度的 substring 都填完。

class Solution {
public:
    int countSubstrings(string s) {

        int len = s.length();
        int result = len;
        vector<vector<int>> dp(len, vector<int>(len, 0));
        for (int i=0; i<len; i++) {
            dp[i][i] = 1;
        }
        for (int i=0; i<len-1; i++) {
            if (s[i] == s[i+1]) {
                dp[i][i+1] = 1;
                result++;
            }
        }

        for (int i=3; i<=len; i++) {
            for (int left = 0; left<=len-i; left++) {
                if (s[left] == s[left+i-1] && dp[left+1][left+i-1-1] == 1) {
                    dp[left][left+i-1] = 1;
                    result++;
                }
            }
        }
        return result;
    }
};

複雜度

時間複雜度部分，總共可以找出 n * (n-1)/2 個 substring ，每個 substring 由於有 state variable ，不用逐一確認每個 substring ，因此可以說只需要 constant time 就可以處理每個 substring ，因此時間複雜度為 O(n^2) 。

空間複雜度就是一個二維陣列 O(n^2) 。