1
00:00:00,320 --> 00:00:01,460
Welcome back.

2
00:00:01,760 --> 00:00:08,090
In the previous video, we have discussed the recursive approach for solving the LCS question.

3
00:00:08,090 --> 00:00:12,410
Let's now write the pseudo code for implementing this in code.

4
00:00:12,410 --> 00:00:14,330
So we will have a function.

5
00:00:14,510 --> 00:00:17,060
And this function will have some inputs.

6
00:00:17,060 --> 00:00:22,820
And inside the function we will have to write the base case and the choice diagram.

7
00:00:22,820 --> 00:00:25,700
Now we had previously discussed the base case.

8
00:00:25,700 --> 00:00:33,920
So if I is greater than n minus one or j is greater than m minus one, where n and m are the lengths

9
00:00:33,920 --> 00:00:41,120
of the two texts or strings given to us, and I is used to iterate over text one and j is used to iterate

10
00:00:41,120 --> 00:00:43,070
over the characters of text two.

11
00:00:43,100 --> 00:00:48,980
So if either of this has happened, then we would have hit the base case, and in that case we can just

12
00:00:48,980 --> 00:00:50,120
return zero.

13
00:00:50,180 --> 00:00:54,830
Now, when it comes to the choice diagram, remember there are two possibilities.

14
00:00:54,860 --> 00:01:00,650
Now in the inputs over here we would be passing two indices I and J.

15
00:01:00,650 --> 00:01:06,860
Now I would be the index that we would be considering in text one, and j would be the index that we

16
00:01:06,860 --> 00:01:09,170
would be considering in text two.

17
00:01:09,200 --> 00:01:15,740
Now, if these two characters, that is, if the character in text one at index I, and if the character

18
00:01:15,740 --> 00:01:18,080
in text two at index j.

19
00:01:18,080 --> 00:01:27,080
If these two are equal, then we would have to find one plus the LCS in the remaining two parts of the

20
00:01:27,080 --> 00:01:28,160
two strings.

21
00:01:28,310 --> 00:01:35,630
Now, if these two are not equal, then as we have seen, we have to call the same function recursively

22
00:01:35,630 --> 00:01:36,230
twice.

23
00:01:36,230 --> 00:01:37,910
So let's call it just f.

24
00:01:37,910 --> 00:01:40,670
So in one case we would increment I.

25
00:01:40,700 --> 00:01:43,940
So the input would be I plus one and j.

26
00:01:43,940 --> 00:01:46,760
And the other case we would keep I as it is.

27
00:01:46,760 --> 00:01:48,710
And we would have to increment j.

28
00:01:48,710 --> 00:01:56,450
And then we would have to find the maximum between these two which would give the longest common subsequence

29
00:01:56,450 --> 00:01:57,080
length.

30
00:01:57,170 --> 00:02:02,810
So this is the pseudocode for the approach that we have discussed for solving the LCS question in a

31
00:02:02,810 --> 00:02:03,770
recursive manner.