DP_C++_3ms_Accepted_Time: O(mn)_Space: O(mn)


  • 0

    Use 2-dimension vector to check each char in s3 and to find out whether it could be connected by its previous char in s1 or s2.
    (I tried to use O(m+n) space but failed, is it possible for O(m+n) ? ; - ) )

    class Solution {
    public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size();//rows
        int n2 = s2.size();//cols
        int n3 = s3.size();
        if(n1 + n2 != n3){return false;}
        else if(n1 == 0 && n2 == 0 && n3 == 0) return true;
        else if(s1[0] != s3[0] && s2[0] != s3[0]) return false;
        
        int dp[n1+1][n2+1] = {0};
        
        for(int i = 1; i <= n1; ++i){
            if(s1[i-1] == s3[i-1]){dp[i][0] = 1;}
            else{break;}
        }
        
        for(int j = 1; j <= n2; ++j){
            if(s2[j-1] == s3[j-1]){dp[0][j] = 1;}
            else{break;}
        }
        
        int ptr = 0;// for s3
        for(int i = 1; i <= n1; ++i){
            for(int j = 1; j <= n2; ++j){
                ptr = i + j;
                if(s3[ptr - 1] == s1[i - 1]){dp[i][j] = dp[i-1][j] || dp[i][j];}
                if(s3[ptr - 1] == s2[j - 1]){dp[i][j] = dp[i][j-1] || dp[i][j];}
                //if(dp[i][j]) ptr++; no need. because we use i and j as the variable.
            }
        }
        return dp[n1][n2];
    }
    };
    

    0_1476134844575_CB4F6B7E-0BA3-4DC4-914C-AA70086AEC9A.png


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.