runtime 0 ms, beats 100% of cpp submissions
O(mn) solution with explanation

tags: recursion, dp

Interleaving String

📖 description

給定三個字串 s1, s2, s3 ，判斷 s3 可不可以被 s1 與 s2 按照順序組合。

ex.
    s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
    
    s1  s2    s1  s2 s1
    aa  dbbc  bc  a  c

    其中一種解法

🧠 solution

本題使用暴力法的時間複雜度為 O(2^(m+n)) ，顯然是不可行的，但我們可以從一些範例中看到有許多部分需要重複計算。

ex.
    s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
    
    s1  s2
    aa  d 

    比如在此狀態下，我們可以從 s1 挑選 b ，也可以從 s2 挑選 b ，當重複的 query 發生時，我們必須重複確認許多已經看過的狀態

於是將以看過的狀態儲存下來，避免重複計算，就可以顯著的減少時間複雜度。

⏳ time complexity

m 表示 s1 的長度，n 表示 s2 的長度
所有狀態的數量為 mn 種，計算複雜度為 O(1)
總時間複雜度 O(mn)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool re(string& s1,string& s2,string& s3,vector<vector<int>>& dp,int i,int j,int k){
        if(dp[i][j]!=-1){       // 如果數值被計算過
            return dp[i][j]==1;
        }
        if(k==s3.size()){       // 配對完成
            return dp[i][j]=true;
        }
        bool flag = false;
        if(i<s1.size() && s3[k]==s1[i]){    // 從 s1 拿
            flag |= re(s1,s2,s3,dp,i+1,j,k+1);
        }
        if(j<s2.size() && s3[k]==s2[j]){    // 從 s2 拿
            flag |= re(s1,s2,s3,dp,i,j+1,k+1);
        }
        return dp[i][j] = (flag==true ? 1 : 0);   // 紀錄狀態
    }
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(),n = s2.size();
        if(m+n!=s3.size()){
            return false;
        }
        vector<vector<int>> dp(m+1,vector<int>(n+1,-1));
        return re(s1,s2,s3,dp,0,0,0);
    }
};