In this lecture, we are going to go over what the longest common common sub sequence is.
And it's a very simple concept to understand.
It's taking two strings as input and figuring out what their longest common sub sequences.
So what I mean by that?
So let's say we have two strings,
and for our first string, we'll keep it simple.
Say A, B, C, D, and then our second string is D, E, f, and G.
Well, in this case, our longest common sub sequence is D because we have a D here and we have a D
here.
And then in another example, let's say we have a c, I, and O, and then down here we have B, oh
I and Z.
Well, we see that we have an I in an O here and an O and an I here.
Therefore our longest common sub sequence is O and I.
Right?
So overall the, the concept there is pretty easy.
So it's not too difficult to kind of understand what we want to do.
But adding in dynamic programming gives it like that little extra layer of complexity.
So for us to kind of figure out how to code this and visually code this because we're not using recursion,
we can use two DX arrays.
So it's going to basically be one big grid and we'll say that our sequence is A, B, C, D, and E,
and then up here we will say that we have a, C and E, so we'll create our grid right here
and finish it up.
But one that was a bad line.
And we got our grid now.
So the first thing that we want to do is basically initialize the outside with all zeros.
That way we know, hey, we've exhausted all possibilities in here.
We completely enumerated every every possible scenario that we can in here.
So the first thing we want to do is we're going to start up in this index right here.
So we see that we're comparing a to an A, which means, yes, they match.
So we can denote this by putting a one.
Well, when you have a match, you're going to move diagonally.
So we know we have something here that can contribute to our longest common subsequent.
So we want to move diagonally.
So we're done with the A's now.
So now we are comparing BCD and E to C and E, Well, we see that B and C obviously don't match.
So we can put a zero here.
And when you don't have a match here, then you want to check to the right and you want to check down.
Well, we see that B an e do not match, so we can put a zero here and now we want to move down.
So we're done with B.
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
C, so we put a one here and now that we have R one, we're going to move diagonal again.
So now we're at the D level, so we're going to compare D and E
to E, so we know that D and E are not the same.
So we put a zero here and we either move to the right or we move down.
Well, we see that we already have our zero here, so we know we're not going to the right and now we've
got to move down.
So now we're comparing E to E, which means that we have a one.
So now we either go to the or excuse me, and since we have a match, we move diagonally.
And since we see we have a zero here already, we're done.
So for us to figure out our longest common subsequent, we are going to go from we're going to do zero
plus one because we're basically we're going to move up our path that we just traversed down on.
So we're going back up.
So we go zero plus one.
So this would be our E.
So now that we're here, we go up, we see that we have a zero.
Now we're going to go back over to our one, which is going to be our C.
So now we have that.
So that would be another plus zero plus one.
And then we're going do another.
We're going to move up one, which is going to be a zero, and then we're going to move diagonal one,
which is going to be our last A So currently our longest common sub sequence is E, C, and A, and
if we want to put this in the order in which we traversed it down, we can just simply call reverse
on it.
And now we have our longest common sub sequence of a C and E, which you don't have to reverse it.
I just like to do it personally.
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
our C and we have our E, So we definitely have the correct solutions.
So again, we start in the top left corner.
We work our way down and then once we know that we have enumerated every possibility, we work our way
back up to rebuild our longest common subsequent.
So now that we have a really good understanding of how this algorithm works, we are going to go implement
it in in the next lecture.