Welcome back.
Let's now get into the code for the tabulation approach for solving the LCS question okay.
So we are given two strings.
We have text one and text two.
Now let's say n and m are the length of text one and text two respectively.
So const n is equal to text one dot length okay and const m is equal to text two dot length.
All right.
And then because this is the tabulation approach and as we have discussed in the previous video, we
would need a 2D dp array which has n plus one rows and m plus one columns.
So let's create that okay.
So const dp is equal to array dot from and you have length n plus one over here okay.
And over here we would need m columns.
So I have array m plus one okay.
And what we're going to do over here is we're going to fill every cell in this DP array with the value
zero.
All right.
Now, we have seen in the previous video that we would want to initialize the first row and the first
column with the value zero.
But that's taken care over here okay.
So we don't need to write explicitly more code to achieve that.
Now let's go ahead and iterate through the remaining cells in the DP array.
And for that I will use a nested for loop.
And we will start with I equal to one because we don't need to visit the zeroth row.
Okay.
Because that's already made to zero as we have discussed over here.
So let I is equal to one and I less than equal to n because we have n plus one rows.
So the row indices go from zero up to n okay.
So I less than equal to n I plus plus.
And for j is equal to one.
Again we don't need to visit the column with index zero because we have already filled those values
to zero over here.
So for let j is equal to one j less than equal to m j plus plus.
Okay, now there are two possibilities.
The first possibility is that the characters that we are comparing are equal.
And if that is the case, as we have discussed in the previous video, we will assign depee at I j to
be equal to one plus the left diagonal top element.
Okay.
So let's go ahead and write the code for that.
So if text one at index I minus one is equal to text two at index j minus one.
So if these are equal then we'll say depee at I j is equal to one plus dp at I minus one j minus one.
Okay.
Now again notice this is the left diagonal element in the previous row.
And we have discussed this in detail in the previous video.
And over here we have I minus one and j minus one.
Because we have to convert the index that we are getting from the DP table to a zero indexed index,
because text one and text two are zero indexed.
For example, the first character in text one and text two will be at index zero, but in the DP table
it would be at index one, respectively.
Now again, I'm not going to repeat this over here.
We have already discussed this in detail in the previous video.
So again quickly just reviewing it.
So the reason why we have I minus one over here and over here are different reasons.
All right.
Now the other possibility is that these two characters, which we are comparing are not equal.
And if that is the case, then DP at ij would be equal to the maximum between the value to the left
of dp at ij and to the top of dp at ij, and to get the value to the left of dp at ij.
We just have to do dp at I j minus one, right.
So again let's write that.
So we have dp at I and j minus one.
So this would give us the value to the left of dp at ij and the value to the top of dp at ij would be
dp at I minus one j okay.
So the maximum between these two would be assigned to dp at ij.
So that's it.
Now once we are out of the for loop we would just have to return dp at n m.
Which is the last cell in the DP table.
So this should solve the question.
And again it's been so easy to go ahead and implement this because first we have written the recursive
solution and then we have memorized it.
And we have thoroughly understood the recurrence relation over there.
And that has helped us to easily go ahead and implement the tabulation approach.
Now let's go ahead and run this code and check whether it's passing all the test cases.
And you can see that it's passing all the test cases.