What does "dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];" this mean?

user_15034627 0
Viewed 105

Can anyone help me in getting my this doubt clear:

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];  
    }

I want to know the meaning of the following line:

for(int i2 = 1; i2 <= n2; i2++) dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];

Is it performing some conditional check or what?

I got this statement while reading some question related to dynamic programming.

dynamic-programming c++
3 Answers

It is a concise form of testing two conditions and assigning the logical result.

dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1]

dp[0][i2] = ((dp[0][i2 - 1] != false) && (s2[i2 - 1] == s3[i2 - 1]))) ? true : false;

if ((dp[0][i2 - 1] != false) && (s2[i2 - 1] == s3[i2 - 1])))
{
  dp[0][i2] = true;
}
else
{
  dp[0][i2] = false;
}
user_115270760 
for(int i2 = 1; i2 <= n2; i2++){
    dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];
}

The above for loop is iterating on the range [1, n2] i.e 1 to n2 including both.

dp is a 2D array storing boolean values where boolean is calculated on the basis of the previous column value of the same row of dp array i.e 0th row here and also checking if the string s2 and s3 have the same character at index i2-1.

Let me give an example to state the same: -

Let's says your dp array is as below: -

-----------------------------
| True | True | False| True |
| True | False| True | True |
| False| True | False| True |
-----------------------------

It has 3 rows and 4 columns.

And also let's consider the two strings as below: -

s2 = "ROOT" s3 = "MOLE"

as the code is iterating 0th row only, so let's consider your i2 as 2.

So as you see dp[0][i2] = "False" and dp[0][i2-1] = "True" with i2 as 2

and when you compare the characters from the string s1 and s2 at index i2-1 i.e 1, so s1[i2-1] == s2[i2-1] is true as the characters at both the places are same: s1[i2-1] = s2[i2-1] = 'O'

So combining the conditions dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1] will give you True && True which is True and the code will update the value of dp[0][i2] as True

user_76605870 
for(int i2 = 1; i2 <= n2; i2++){ 
     dp[0][i2] = dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1];
}

Every expression returns a value, the expression s2[i2 - 1] == s3[i2 - 1] will either result 1 or 0. When && operator is used then it converts everything into boolean. Every non-zero value is considered as 1 and every zero value is considered 0. Hence an expression like (3 && 6) will return 1.

dp[0][i2 - 1] && s2[i2 - 1] == s3[i2 - 1] will be evaluated in the same fashion. == has more presedence than && therefore it will be evaluated first. So s2[i2 - 1] == s3[i2 - 1] will return a boolean value which will then be evaluated with dp[0][i2 - 1] && x, where x is the value returned from s2[i2 - 1] == s3[i2 - 1]. It finally will evaluate into a boolean value which will be stored in dp[0][i2].

user_140303530
Related