1
00:00:00,110 --> 00:00:01,010
Welcome back.

2
00:00:01,010 --> 00:00:07,010
Let's now get into the code for the tabulation approach for solving the LCS question okay.

3
00:00:07,010 --> 00:00:08,420
So we are given two strings.

4
00:00:08,420 --> 00:00:10,220
We have text one and text two.

5
00:00:10,250 --> 00:00:15,740
Now let's say n and m are the length of text one and text two respectively.

6
00:00:15,740 --> 00:00:24,200
So const n is equal to text one dot length okay and const m is equal to text two dot length.

7
00:00:25,040 --> 00:00:25,550
All right.

8
00:00:25,550 --> 00:00:30,770
And then because this is the tabulation approach and as we have discussed in the previous video, we

9
00:00:30,770 --> 00:00:37,100
would need a 2D dp array which has n plus one rows and m plus one columns.

10
00:00:37,100 --> 00:00:38,480
So let's create that okay.

11
00:00:38,480 --> 00:00:47,420
So const dp is equal to array dot from and you have length n plus one over here okay.

12
00:00:48,200 --> 00:00:52,280
And over here we would need m columns.

13
00:00:52,280 --> 00:00:56,570
So I have array m plus one okay.

14
00:00:56,570 --> 00:01:02,660
And what we're going to do over here is we're going to fill every cell in this DP array with the value

15
00:01:02,660 --> 00:01:03,200
zero.

16
00:01:04,120 --> 00:01:04,720
All right.

17
00:01:04,720 --> 00:01:11,260
Now, we have seen in the previous video that we would want to initialize the first row and the first

18
00:01:11,260 --> 00:01:12,670
column with the value zero.

19
00:01:12,670 --> 00:01:14,950
But that's taken care over here okay.

20
00:01:14,950 --> 00:01:18,790
So we don't need to write explicitly more code to achieve that.

21
00:01:18,790 --> 00:01:23,260
Now let's go ahead and iterate through the remaining cells in the DP array.

22
00:01:23,260 --> 00:01:26,020
And for that I will use a nested for loop.

23
00:01:26,860 --> 00:01:32,560
And we will start with I equal to one because we don't need to visit the zeroth row.

24
00:01:32,590 --> 00:01:33,040
Okay.

25
00:01:33,040 --> 00:01:36,640
Because that's already made to zero as we have discussed over here.

26
00:01:36,640 --> 00:01:43,420
So let I is equal to one and I less than equal to n because we have n plus one rows.

27
00:01:43,420 --> 00:01:47,620
So the row indices go from zero up to n okay.

28
00:01:47,620 --> 00:01:50,410
So I less than equal to n I plus plus.

29
00:01:50,410 --> 00:01:54,790
And for j is equal to one.

30
00:01:54,790 --> 00:02:00,160
Again we don't need to visit the column with index zero because we have already filled those values

31
00:02:00,160 --> 00:02:01,060
to zero over here.

32
00:02:01,060 --> 00:02:08,140
So for let j is equal to one j less than equal to m j plus plus.

33
00:02:09,310 --> 00:02:12,220
Okay, now there are two possibilities.

34
00:02:12,220 --> 00:02:17,950
The first possibility is that the characters that we are comparing are equal.

35
00:02:17,950 --> 00:02:23,650
And if that is the case, as we have discussed in the previous video, we will assign depee at I j to

36
00:02:23,650 --> 00:02:28,210
be equal to one plus the left diagonal top element.

37
00:02:28,210 --> 00:02:28,540
Okay.

38
00:02:28,540 --> 00:02:30,550
So let's go ahead and write the code for that.

39
00:02:30,550 --> 00:02:42,010
So if text one at index I minus one is equal to text two at index j minus one.

40
00:02:42,010 --> 00:02:53,650
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.

41
00:02:53,650 --> 00:02:54,250
Okay.

42
00:02:54,250 --> 00:03:00,460
Now again notice this is the left diagonal element in the previous row.

43
00:03:00,460 --> 00:03:03,130
And we have discussed this in detail in the previous video.

44
00:03:03,130 --> 00:03:07,810
And over here we have I minus one and j minus one.

45
00:03:07,810 --> 00:03:15,850
Because we have to convert the index that we are getting from the DP table to a zero indexed index,

46
00:03:15,850 --> 00:03:19,240
because text one and text two are zero indexed.

47
00:03:19,240 --> 00:03:25,840
For example, the first character in text one and text two will be at index zero, but in the DP table

48
00:03:25,840 --> 00:03:27,640
it would be at index one, respectively.

49
00:03:27,640 --> 00:03:30,040
Now again, I'm not going to repeat this over here.

50
00:03:30,040 --> 00:03:33,220
We have already discussed this in detail in the previous video.

51
00:03:33,220 --> 00:03:35,170
So again quickly just reviewing it.

52
00:03:35,170 --> 00:03:40,240
So the reason why we have I minus one over here and over here are different reasons.

53
00:03:40,240 --> 00:03:40,900
All right.

54
00:03:40,900 --> 00:03:46,570
Now the other possibility is that these two characters, which we are comparing are not equal.

55
00:03:46,570 --> 00:03:55,900
And if that is the case, then DP at ij would be equal to the maximum between the value to the left

56
00:03:55,900 --> 00:04:02,590
of dp at ij and to the top of dp at ij, and to get the value to the left of dp at ij.

57
00:04:02,620 --> 00:04:05,980
We just have to do dp at I j minus one, right.

58
00:04:05,980 --> 00:04:07,180
So again let's write that.

59
00:04:07,180 --> 00:04:10,780
So we have dp at I and j minus one.

60
00:04:10,780 --> 00:04:18,130
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

61
00:04:18,130 --> 00:04:21,100
dp at I minus one j okay.

62
00:04:21,100 --> 00:04:25,600
So the maximum between these two would be assigned to dp at ij.

63
00:04:25,720 --> 00:04:26,620
So that's it.

64
00:04:26,620 --> 00:04:32,560
Now once we are out of the for loop we would just have to return dp at n m.

65
00:04:33,200 --> 00:04:36,440
Which is the last cell in the DP table.

66
00:04:36,440 --> 00:04:38,090
So this should solve the question.

67
00:04:38,090 --> 00:04:44,180
And again it's been so easy to go ahead and implement this because first we have written the recursive

68
00:04:44,180 --> 00:04:46,400
solution and then we have memorized it.

69
00:04:46,400 --> 00:04:50,900
And we have thoroughly understood the recurrence relation over there.

70
00:04:50,900 --> 00:04:55,790
And that has helped us to easily go ahead and implement the tabulation approach.

71
00:04:55,790 --> 00:05:01,040
Now let's go ahead and run this code and check whether it's passing all the test cases.

72
00:05:01,640 --> 00:05:04,670
And you can see that it's passing all the test cases.