1
00:00:06,750 --> 00:00:13,380
In this lecture, we are going to go over what the longest common common sub sequence is.

2
00:00:14,760 --> 00:00:17,520
And it's a very simple concept to understand.

3
00:00:18,090 --> 00:00:26,790
It's taking two strings as input and figuring out what their longest common sub sequences.

4
00:00:27,030 --> 00:00:28,230
So what I mean by that?

5
00:00:28,230 --> 00:00:29,970
So let's say we have two strings,

6
00:00:33,690 --> 00:00:36,090
and for our first string, we'll keep it simple.

7
00:00:36,090 --> 00:00:44,340
Say A, B, C, D, and then our second string is D, E, f, and G.

8
00:00:45,090 --> 00:00:55,200
Well, in this case, our longest common sub sequence is D because we have a D here and we have a D

9
00:00:55,200 --> 00:00:55,800
here.

10
00:00:57,120 --> 00:01:04,850
And then in another example, let's say we have a c, I, and O, and then down here we have B, oh

11
00:01:04,860 --> 00:01:06,330
I and Z.

12
00:01:07,050 --> 00:01:14,790
Well, we see that we have an I in an O here and an O and an I here.

13
00:01:15,030 --> 00:01:21,150
Therefore our longest common sub sequence is O and I.

14
00:01:22,110 --> 00:01:22,530
Right?

15
00:01:22,530 --> 00:01:28,290
So overall the, the concept there is pretty easy.

16
00:01:28,290 --> 00:01:33,450
So it's not too difficult to kind of understand what we want to do.

17
00:01:34,020 --> 00:01:39,090
But adding in dynamic programming gives it like that little extra layer of complexity.

18
00:01:39,540 --> 00:01:47,250
So for us to kind of figure out how to code this and visually code this because we're not using recursion,

19
00:01:47,640 --> 00:01:52,170
we can use two DX arrays.

20
00:01:52,170 --> 00:02:05,310
So it's going to basically be one big grid and we'll say that our sequence is A, B, C, D, and E,

21
00:02:05,880 --> 00:02:15,690
and then up here we will say that we have a, C and E, so we'll create our grid right here

22
00:02:20,400 --> 00:02:25,140
and finish it up.

23
00:02:29,190 --> 00:02:31,830
But one that was a bad line.

24
00:02:34,310 --> 00:02:36,230
And we got our grid now.

25
00:02:36,620 --> 00:02:42,670
So the first thing that we want to do is basically initialize the outside with all zeros.

26
00:02:42,680 --> 00:02:51,890
That way we know, hey, we've exhausted all possibilities in here.

27
00:02:51,890 --> 00:02:57,950
We completely enumerated every every possible scenario that we can in here.

28
00:02:59,090 --> 00:03:05,240
So the first thing we want to do is we're going to start up in this index right here.

29
00:03:06,080 --> 00:03:14,330
So we see that we're comparing a to an A, which means, yes, they match.

30
00:03:14,330 --> 00:03:17,990
So we can denote this by putting a one.

31
00:03:18,530 --> 00:03:22,250
Well, when you have a match, you're going to move diagonally.

32
00:03:23,530 --> 00:03:31,750
So we know we have something here that can contribute to our longest common subsequent.

33
00:03:31,750 --> 00:03:33,570
So we want to move diagonally.

34
00:03:33,580 --> 00:03:35,530
So we're done with the A's now.

35
00:03:36,100 --> 00:03:48,130
So now we are comparing BCD and E to C and E, Well, we see that B and C obviously don't match.

36
00:03:48,280 --> 00:03:50,200
So we can put a zero here.

37
00:03:50,830 --> 00:03:58,510
And when you don't have a match here, then you want to check to the right and you want to check down.

38
00:04:01,920 --> 00:04:09,090
Well, we see that B an e do not match, so we can put a zero here and now we want to move down.

39
00:04:09,180 --> 00:04:10,920
So we're done with B.

40
00:04:13,470 --> 00:04:23,160
So now we're at C, so we're comparing C, D, and E to see an E, Well, we see that we have C and

41
00:04:23,160 --> 00:04:30,750
C, so we put a one here and now that we have R one, we're going to move diagonal again.

42
00:04:32,100 --> 00:04:36,120
So now we're at the D level, so we're going to compare D and E

43
00:04:38,940 --> 00:04:43,260
to E, so we know that D and E are not the same.

44
00:04:43,260 --> 00:04:48,750
So we put a zero here and we either move to the right or we move down.

45
00:04:49,500 --> 00:04:55,350
Well, we see that we already have our zero here, so we know we're not going to the right and now we've

46
00:04:55,350 --> 00:04:56,310
got to move down.

47
00:04:56,310 --> 00:05:01,470
So now we're comparing E to E, which means that we have a one.

48
00:05:01,560 --> 00:05:08,250
So now we either go to the or excuse me, and since we have a match, we move diagonally.

49
00:05:08,370 --> 00:05:11,970
And since we see we have a zero here already, we're done.

50
00:05:12,630 --> 00:05:22,830
So for us to figure out our longest common subsequent, we are going to go from we're going to do zero

51
00:05:23,790 --> 00:05:29,100
plus one because we're basically we're going to move up our path that we just traversed down on.

52
00:05:29,100 --> 00:05:30,510
So we're going back up.

53
00:05:30,810 --> 00:05:33,270
So we go zero plus one.

54
00:05:33,270 --> 00:05:35,100
So this would be our E.

55
00:05:37,500 --> 00:05:41,820
So now that we're here, we go up, we see that we have a zero.

56
00:05:41,850 --> 00:05:47,400
Now we're going to go back over to our one, which is going to be our C.

57
00:05:48,570 --> 00:05:49,740
So now we have that.

58
00:05:49,740 --> 00:05:53,640
So that would be another plus zero plus one.

59
00:05:55,290 --> 00:05:56,610
And then we're going do another.

60
00:05:56,640 --> 00:06:02,760
We're going to move up one, which is going to be a zero, and then we're going to move diagonal one,

61
00:06:02,910 --> 00:06:12,180
which is going to be our last A So currently our longest common sub sequence is E, C, and A, and

62
00:06:12,180 --> 00:06:17,850
if we want to put this in the order in which we traversed it down, we can just simply call reverse

63
00:06:17,850 --> 00:06:18,540
on it.

64
00:06:19,950 --> 00:06:28,620
And now we have our longest common sub sequence of a C and E, which you don't have to reverse it.

65
00:06:28,620 --> 00:06:31,020
I just like to do it personally.

66
00:06:31,830 --> 00:06:44,280
So now we have a C and E, and if we look at a C and E to A, B, C, D, e, we have our A, we have

67
00:06:44,280 --> 00:06:50,670
our C and we have our E, So we definitely have the correct solutions.

68
00:06:50,670 --> 00:06:53,790
So again, we start in the top left corner.

69
00:06:53,790 --> 00:07:01,470
We work our way down and then once we know that we have enumerated every possibility, we work our way

70
00:07:01,470 --> 00:07:05,820
back up to rebuild our longest common subsequent.

71
00:07:06,360 --> 00:07:13,380
So now that we have a really good understanding of how this algorithm works, we are going to go implement

72
00:07:13,380 --> 00:07:15,480
it in in the next lecture.