C# DP solution : With thought process


  • 0
    D

    Pretty Neat DP problem ..
    The brute force solution sounds exponential .. given that to exhaust all options for s3 of length N, we need to choose N times whether to pick the character i from s1 or s2.

    An interview problem with exponential brute force solution is almost 90+% really a DP one.

    Define the state DP[i,j] = True if and only if S1{0-->i} Interleaved with S2{0-->j} will result in S3{0-->i+j}

    A closer look may show that DP[i,j] == true if

      1. DP[i-1,j] = true AND S3[i+j] = s1[i] (thus we picked the new char from s1)
    

    OR

      2. DP[i,j-1] = true AND S3[i+j] = s2[j] (thus we picked the new char from s2)
    

    here's the code:

    public bool IsInterleave(string s1, string s2, string s3) {
        if(s3.Length != s1.Length + s2.Length) return false;
        
        bool[,] dp = new bool[s1.Length+1, s2.Length+1];
        dp[0,0] = true;
        for(int i=1; i <= s1.Length; i++){
            dp[i,0] = dp[i-1,0] && s3[i-1] == s1[i-1];
        }
        
        for(int i=1; i <= s2.Length; i++){
            dp[0,i] = dp[0,i-1] && s3[i-1] == s2[i-1];
        }
        
        for(int i=1; i <= s1.Length; i++){
            for(int j=1; j <= s2.Length; j++){
                dp[i,j] = (dp[i-1,j] && s3[i+j-1] == s1[i-1]) || (dp[i,j-1] && s3[i+j-1] == s2[j-1]);
            }
        }
        
        return dp[s1.Length, s2.Length];
    }

Log in to reply
 

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