C++ dp solution with explanation


  • 6

    First tried brute force backtracking, it's obvious will not be accepted.

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
            if(n1 + n2 != n3) return false;
            return isInterleaveHelper(s1, 0, n1, s2, 0, n2, s3, 0, n3);
        }
        
        bool isInterleaveHelper(string &s1, int i1, int n1, string &s2, int i2, int n2, string &s3, int i3, int n3){
            if(i1 == n1 && i2 == n2 && i3 == n3) return true; 
            if(i1 < n1 && s1[i1] == s3[i3] && isInterleaveHelper(s1, i1 + 1, n1, s2, i2, n2, s3, i3 + 1, n3)) return true;
            if(i2 < n2 && s2[i2] == s3[i3] && isInterleaveHelper(s1, i1, n1, s2, i2 + 1, n2, s3, i3 + 1, n3)) return true;
            else return false;
        }
    };
    

    Then it comes to dp solution. I first built a two dimension dp table, with drawing the path displayed below. Because it's interleaving, so certain order still needs to maintain, so that's why for a valid path, it can only go right or down, so that's why dp[i1][i2] is depending on dp[i1 - 1][i2] and dp[i1][i2 - 1]. After discovering the transition rule to get dp[i1][i2], we just need to record true or false in the dp table. dp[i1][i2] means if s3.substr(0, i1 + i2) can be formed by s1.substr(0, i1) interleaving s2.substr(0, i2);

    s3 = “aadbbcbcac”
                     a	    a	    b	    c	   c
    		    0	 1	    2	    3	    4	   5
    
         	0	“”→	 a  →   aa	
    				        ↓
       d	1			    aad  →  aadb
    				        ↓	    ↓
       b	2			    aadb →  aadbb → aadbbc
    				        ↓		↓
       b	3			    aadbb	aadbbcb
    				        ↓
       c	4			    aadbbc→ aadbbcb
    
       a	5
    

    code, O(n1n2) space, and O(n1n2)time, it's much better than the brute force now.

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int n1 = (int)s1.size(), n2 = (int)s2.size(), n3 = (int)s3.size(); 
            if(n1 + n2 != n3) return false;
            
            vector<vector<bool>> dp(n1 + 1, vector<bool>(n2 + 1, false));
            dp[0][0] = true;
            
            for(int i2 = 1; i2 <= n2; i2++) dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];
            for(int i1 = 1; i1 <= n1; i1++) dp[i1][0] = dp[i1 - 1][0] && s1[i1 - 1] == s3[i1 - 1];
    
            for(int i1 = 1; i1 <= n1; i1++){
                for(int i2 = 1; i2 <= n2; i2++){
                    dp[i1][i2] = (dp[i1 - 1][i2] && s1[i1 - 1] == s3[i1 + i2 - 1]) || (dp[i1][i2 - 1] && s2[i2 - 1] == s3[i1 + i2 - 1]);
                }
            }
            
            return dp[n1][n2];  
        }
    };

  • 0
    W

    Great explanation. Thank you so much!


Log in to reply
 

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