Concise 1-D DP c++ solution with explanation


  • 1
    T

    Let's look at a sample case, s1 = "ab", s2 = "ac", s3 ="aabc". We can form 2-D dp matrix as following:

       j   0       1       2       3
     i *-- a --*-- a --*-- b --*-- c --*   
     0 0   1       2      -1      -1
     1 a   0       1      -1      -1  
     2 b  -1      -1       1       2
    

    Let's look at the matrix. For an entry in the matrix, the row index i represents the number of letters used from s1, the entry represents the number of letters used in s2, and the column index j + 1 represents the length of s3 being considered. For example, the entry at coordinate (i=0,j=1) = 2 means that to form the sequence "aa", we use 0 letters from s1 and 2 letters from s2. An entry of "-1" means it is impossible to form s3 at that location.

    The first column of dp can be formed by simply comparing the first character of s3 with the first character of s1 and s2. Given that a current substring of s3 can be matched, there are two ways for the next character to match: 1, the new char must match the next char from s2; 2, the new char must match the next char from s1. Matching with s1 corresponds with adding 1 to the entry on the left; matching with s2 corresponds to copying the value from the top left entry.

    A 2-D matrix is not necessary. A 1-D array which record the column of the matrix would be sufficient. See the following implementation.

    class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            int N_s1 = s1.length();
            int N_s2 = s2.length();
            int N_s3 = s3.length();
            
            // take care of edge cases
            if (N_s3 != N_s1 + N_s2) return false;
            if (N_s2 == 0) return s1.compare(s3) == 0;
            if (N_s1 == 0) return s2.compare(s3) == 0;
            
            // dp starts here 
            vector<int> dp(N_s1+1, -1);
            if (s3[0] == s2[0]) dp[0] = 1;
            if (s3[0] == s1[0]) dp[1] = 0;
            
            for (int i = 1; i < N_s3; ++i){   // loop through s3
                for(int j = N_s1; j >-1 ; --j){ // loop through s1, j corresponds to # of letters used in s1 
                    if (dp[j] != -1 && dp[j] < N_s2 && s3[i] == s2[dp[j]]) dp[j]++;
                    else if (j>0 && dp[j-1] != -1 && s3[i] == s1[j-1]) dp[j] = dp[j-1];
                    else dp[j] = -1;
                }
            }
            
            
            return dp[N_s1] != -1;
            
            
        }
    };

  • 0
    H

    thanks but the first paragraph is a little confusing


  • 0
    S

    The first paragraph is very confusing. Can't make sense of it. for instance "(0,1) = 2, and it means that to form the sequence "aa", 0 letters is used from the s1 sequence and 2 letters are used from the s2 sequence". Are you sure you are talking about the same problem?


Log in to reply
 

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