1
00:00:00,470 --> 00:00:07,700
Let's now get into the code and write the recursive solution for solving the longest common subsequence

2
00:00:07,700 --> 00:00:08,270
question.

3
00:00:08,270 --> 00:00:10,910
So again this is going to be a recursive solution.

4
00:00:10,910 --> 00:00:13,160
And we would need a helper function.

5
00:00:13,160 --> 00:00:15,230
Let me just call it helper itself.

6
00:00:15,230 --> 00:00:20,450
And to this function we will be passing index one and index two.

7
00:00:20,450 --> 00:00:26,690
So these are two variables which will indicate the indices in text one and text two respectively that

8
00:00:26,690 --> 00:00:27,890
we want to compare.

9
00:00:27,890 --> 00:00:28,370
Okay.

10
00:00:28,370 --> 00:00:32,090
So again let's write the details of this function later.

11
00:00:32,090 --> 00:00:39,170
But we will write this function in a way that this will return the longest common subsequence okay.

12
00:00:39,170 --> 00:00:42,920
So it will return the length of the longest common subsequence.

13
00:00:42,920 --> 00:00:47,120
And over here we would have to call this function for the first time.

14
00:00:47,120 --> 00:00:53,720
And when we call it for the first time, we either will be passing the first index for text one and

15
00:00:53,720 --> 00:00:57,980
text two, or the last index for these two texts.

16
00:00:57,980 --> 00:01:01,550
And again, it depends on how we write the recursive solution.

17
00:01:01,550 --> 00:01:06,890
We have discussed many times that you can write the recursive solution, either going from zero to the

18
00:01:06,890 --> 00:01:10,460
last index, or going from the last index to zero.

19
00:01:10,460 --> 00:01:10,850
Okay.

20
00:01:10,850 --> 00:01:13,970
Now over here, let's go from zero to the last index.

21
00:01:13,970 --> 00:01:16,610
And therefore I will be passing zero comma zero.

22
00:01:16,610 --> 00:01:19,790
And we can just in fact return whatever we get over here.

23
00:01:19,790 --> 00:01:25,310
Because as we have mentioned this function over here, the helper function will return the longest common

24
00:01:25,310 --> 00:01:26,120
subsequence.

25
00:01:26,120 --> 00:01:29,540
So this is the skeleton of the approach that we are going to implement.

26
00:01:29,540 --> 00:01:31,670
Now let's go ahead and write the details.

27
00:01:31,670 --> 00:01:38,180
So for the helper function we will be writing the base case as well as the recursive case.

28
00:01:38,990 --> 00:01:44,630
Now when it comes to the base case, as we have discussed in the previous video, it would be the case

29
00:01:44,630 --> 00:01:48,140
when we are encountering the first invalid input.

30
00:01:48,140 --> 00:01:54,350
And because we are going from zero to the last index, the invalid input would be the case where we

31
00:01:54,350 --> 00:01:56,270
are going beyond the last index.

32
00:01:56,270 --> 00:01:56,540
Okay.

33
00:01:56,540 --> 00:02:00,440
So again over here let's define the length of text one and text two.

34
00:02:00,440 --> 00:02:11,600
So let's say const n is equal to text one dot length and const m is equal to text two dot length.

35
00:02:12,860 --> 00:02:20,540
Now over here, if index one is greater than or equal to n, then we would have hit an invalid input

36
00:02:20,540 --> 00:02:20,960
okay.

37
00:02:20,960 --> 00:02:22,370
And that would be the base case.

38
00:02:22,370 --> 00:02:30,230
And in the case of text two that would be if index two is greater than or equal to m okay.

39
00:02:30,230 --> 00:02:34,610
So if we have hit the base case then we can just return zero.

40
00:02:34,610 --> 00:02:40,880
Because either of these texts, either text one or text two, does not have any more characters.

41
00:02:40,880 --> 00:02:45,620
And if that is the case, there would be nothing in common between the two texts, right?

42
00:02:45,620 --> 00:02:53,480
For example, let's say text one is a, b, c, and let's say text two is a, b, d, e f.

43
00:02:53,480 --> 00:03:00,470
Now if we reach over here, which is beyond the last valid index for text one and for text two, if

44
00:03:00,470 --> 00:03:06,710
we are over here, notice that we are actually comparing an empty string and f, and between these two

45
00:03:06,710 --> 00:03:08,420
there are no common characters.

46
00:03:08,420 --> 00:03:10,880
And that's why we can return zero over here.

47
00:03:10,880 --> 00:03:13,880
Okay, now let's proceed to the recursive case.

48
00:03:13,880 --> 00:03:23,630
What we will be checking over here is we will check if text one at index one is equal to text two at

49
00:03:23,630 --> 00:03:24,440
index two.

50
00:03:24,440 --> 00:03:28,790
So if these two are equal then we have found a common character.

51
00:03:28,790 --> 00:03:35,900
And therefore we will just return one plus whatever we get when we call the helper function with higher

52
00:03:35,900 --> 00:03:37,520
index one and index two.

53
00:03:37,550 --> 00:03:43,730
So to this recursive call to the helper function, we will pass the inputs as index one plus one and

54
00:03:43,730 --> 00:03:44,960
index two plus one.

55
00:03:44,960 --> 00:03:51,830
Okay, now if this is not the case then as we have discussed we would have to increment only one index

56
00:03:51,830 --> 00:03:52,520
at a time.

57
00:03:52,520 --> 00:03:55,310
So we'll have to recursively call the helper function.

58
00:03:55,310 --> 00:03:59,060
And in one case we will only increment index one.

59
00:03:59,360 --> 00:04:01,940
And we will keep index two as it is.

60
00:04:01,940 --> 00:04:05,750
And in the other case we will only increment index two.

61
00:04:05,780 --> 00:04:08,060
So index one would be kept as it is.

62
00:04:08,060 --> 00:04:11,600
And for index two we would pass index two plus one.

63
00:04:11,600 --> 00:04:12,020
Okay.

64
00:04:12,020 --> 00:04:16,310
Now between these two whichever gives us the higher value.

65
00:04:16,310 --> 00:04:19,310
That would be what we return in this case okay.

66
00:04:19,310 --> 00:04:22,130
And we have discussed this in detail in the previous video.

67
00:04:22,130 --> 00:04:25,160
So over here let's return math dot max.

68
00:04:25,160 --> 00:04:30,230
And the maximum between what we get over here and over here okay.

69
00:04:30,230 --> 00:04:31,700
And that should be it.

70
00:04:31,700 --> 00:04:33,440
This should help us solve the question.

71
00:04:33,440 --> 00:04:37,220
Now let's go ahead and run this code and see if it's passing all the test cases.

72
00:04:41,700 --> 00:04:43,590
And you can see that it's working.

73
00:04:43,590 --> 00:04:45,390
It's passing all the test cases.