String Interleaving Dynamic Programming

Given three strings, return true if third string is interleaving of first and second string.

[jogindersinghmalik]

Hi, I have one suggestion for your future videos on DP. It will be much better if you could explain briefly why you're considering to apply DP approach on a given problem ( like discussing what kind of optimal substructure or sub-problem do you observe in the problems that make you apply DP on the solution). And I must say your explanation are very effective and useful and concise. I really appreciate it. God bless you!

[starc]

how we will solve this problem? Yes we will use dynamic programming. But i will not tell the 'how', thats the magic.

[maxfeldman]

To all people who were asking why once he checks from left and other time from above. the answer is when the text in the place [I][j] equals the letter in the phrase above so he checks is the left index of it is T, when the letter in [I][j] equals the letter in the phrase to the left, so he checks if the index above is T.
another helpful tip, you can check exactly which variations of text (1) and text (2) can construct the final text ( 3 in he's example), the algorithm is if you have a straight way of T from index [0][0] till index [M][N] without F in between and you can only "move" RIGHT OR BOTTOM
hope I made it more clear..

[harshseth]

[0][0] means both the strings are empty. Hence true. (It would be only true if s3 is also empty ""; this condition is checked before DP table. s1 length + s2 length = s3 length. )
[0][j] means what if s2 = "" and s1!= "" then we compare character by character of column with s3. if any character doesn't match correctly all other column values would be 0.
[i][0] means what if s1 = "" and s2!="" then we compare character by character of row with s3. if any character doesn't match correctly all other row values would be 0.

[i][j] :
if (char at i != char at j and char at i ==s3[i+j-1]) then dp [i][j]=dp[i-1][j]. it means that only s1 char matches with s3 char.. [i-1][j] asks dp table if previous values were correct right? then this is correct too as both character matches.

if (char at i != char at j and char at j == s3[i+j-1]) then dp [i][j]=dp[i][j-1]. it means that only s2 char matches with s3 char .. [i][j-1] asks dp table if previous values were correct right? then this is correct too as both character matches.


if (char at i == char at j && char at i ==s3[i+j-1])
here there is confusion.. should we pick char at i or should we pick char at j. hence let's check both by dp[i-1][j] || dp[i][j-1].. here || (or) means that somehow we are able to reach [i][j] either taking s1 or s2.

Like this DP table is filled. At last [n][m] tell are we able to somehow reach last successfully.

One missing point regarding why we compare s3's index as [i+j-1]? I will leave it to be answered in comments.

Thanks.

[BingumallaAbinay]

what is your intuition for solving this question with DP ?? Also it would have been much better if you explain logic first and then do dry run

[rohitsudhakar]

So how do we solve this question? Yes, let's use dynamic programming.

[mohamedbilal]

I don't understand this. Could somebody give me a better explanation?

[sayanbanerjee]

The formula you have written at the end of the video is opposite of the one you have discussed in the video.
if str1[i]==str3[i+j] then T[i, j]= T[i, j-1]
if str2[j] == str3[i+j] then T[i, j] = T[i-1, j]

[xabialonso]

Hey Tushar,

Thanks for all your DP videos.

Btw, generally speaking when should we use 0th row and 0th column.

In some problems you use 0th row and 0th column, some you just have 0th row. It's confusing. I would appreciate if you explain it a bit further.

Also, in this particular example can you explain in depth as to how you filled 0th row and 0th col? Why is 0, 0 = True?

Thanks.

[rahulreddy]

You can solve this using 1D array too. Its more efficient than this one. But appreciate your effort to explain this.

[shairuno]

It is too bad that you don't explain the intuition behind the algorithm. Then, it becomes just another mechanical way of solving this problem.

[dilkushmalav]

I have one suggestion for your videos. It will be good if you explain the intuition like why are we filling dp table like this or consider each (r, c) as a subproblem.

[m]

How do you pick whether you compare it to the boolean value on the left of the one on the top? For example when ur filling the last row starting at 5:33. You check against the boolean value on the left and later on you check against the boolean value on the top. Could you explain?

[chirrayeshwanthreddy]

it would have been much better if you explain logic first and then do dry run

[cristianouzumaki]

Sir. You missed one condition when both s1 and s2 match with s3.
This condition will pass that.

if(s2.charAt(j-1) == s1.charAt(i-1) && s1.charAt(i-1) == s3.charAt(i+j-1))
ans[i][j] = ans[i-1][j] || ans[i][j-1];

[AmirKhan-smdx]

This guy is the perfect example of knowledge with no teaching skills😁

At one time you were checking top element and at another time, you were checking left element. Please explain

[shrad]

we can also solve this problem using lcs between a &b and b&c and we first check if a+b length is equal to c length, if all these condition return true then return true

[viveikkumaryadav]

got solution but couln't get why we are doing this. the intent behing doing so. if you could explain this we could have better understanding of the dp. thanks

[TheTutorialspoint]

how to  know where to 2 apply Dinamic programming?