In this lecture, we are now going to go over the implementation to the longest common subsequent that
we discussed in the previous lecture.
So we're going to start off with the function initialization longest common sub C quints.
And remember, we want to string.
So we'll do two string slices and we want to return a string with our longest common subsequent given
to us.
So we want to store all the characters into a vector.
So for us to do that, we can say let a vector of type char equal a dot charge dot collect.
So now we just stored all of our A's into a vector and we want to do the same for B.
And so here we are storing all the characters into the vector.
Next, we want to store the lengths of our vectors so we can easily create it by saying let length A
and link B equal to a dot lynne and B dot lynne.
So we want to store the links.
And then lastly or not lastly, next we want to say the solution is from within.
I j is the length of the LCS say lcs longest common sub sequence
and then between a of zero to I minus one and B from zero to J minus one.
So for us to create this solutions vector that we want here, we need to use the links that we generated
here.
So we want the solution
to be a vector and it's going to be contain a vector and this vector is going to be from zero to B plus
one,
and our other vector will be from zero to link a plus one.
And I realized that I need to put those there.
And let me add that there.
All right.
So we just created our solutions vector of links of a from 0 to 1 J minus one and zero to J minus one.
All right, so now we can begin traversing our to DX array from top to bottom.
So we want to enumerate all of our possibilities for that.
So we will say for I of AI.
So we want to iterate here and a dot editor and then remember we want to enumerate.
So luckily Russ gives that to us, so we want to enumerate all the possibilities.
And then for J and M of J and we want to do it the same thing for B, so.
Editor dot enumerate.
So now we're beginning to traverse down.
So if M of I is equal to m of J, there is a new common character.
Otherwise, take the best of the two solutions
at I minus one to j and I to J.
Minus one.
So otherwise.
So if M of a is equal to m of J, there is a new common character.
Otherwise, take the best of the two solutions at I minus one and J and I of J minus one.
So we can very quickly implement this by saying solutions of I plus one and J plus one.
So we're just moving our index in the array equals if I equals of M of J.
So if the solutions are the same or excuse me, if the characters are the same, then we want to say
solutions.
I keep saying solutions solution.
I j plus one.
So we are denoting it that we have a common character by putting the one value there.
So now we say solutions solution of I and now we go j plus one dot max solution I plus one and J And
this max method here that is given to us inside of the vector class is going to compare and return the
maximum two values.
So we're going to compare I and J plus one to solution of I plus one and J.
So now we just implement it in this portion of it.
And so once we've done all that well, then we have completely enumerated our to DX array from top left
to bottom right or basically what we did in the previous lecture.
So now we want to go from the bottom up.
So we want to reconstitute the solution string.
So we want to get our solution string back from the links.
So if remember, if the value is one, then that means we had a common character.
And so we want to take that character and add it into our our solution string, if you will.
So to do this, we'll say let result of a vector type char
equals a new vec and we'll say let mute I and mute J equals to length A and length B.
So while I is greater than zero and J is greater than zero, we want to traverse from the bottom up.
So if I excuse me, if a of I minus one is equal to B of J minus one, then we want to push this result
because that means we have a common character.
So we will say push a of I minus one and now we want to traverse up the array.
So we're going to increment that way.
We go back up to the top else if
solution of I minus one and J is greater than solution of I and J minus one, then we just want to move
up the AI value
else.
Our last case, we just want to move up the j value.
So if they match, move up and increment both of them, if I minus one and J if this index is greater
than this index, then we just increment I otherwise decrement J So again, that is just us traversing
back up from the bottom to the top of our to DX array.
And then as I said, I always like to reverse my string.
That way it's back in kind of the order in which the string was presented to us and then for us to turn
it into our string, we will say result that enter and collect.
And I believe that is all we have to do.
So let me do a cargo bill just to make sure that it runs.
It looks like we're missing something.
What are we missing?
Get rid of that.
That way it is actually returned.
And line 45, I need to add our semicolon.
How about now?
Now we're happy.
All right, so let's add in our test cases now to verify that our LCS function works.
And we'll add in a couple of test cases to kind of vet it.
Very good.
So long as common, subsequent.
And so we'll have an empty test case.
So we will assert equals on our longest common subsequent.
So if they pass in two empty strings, then we expect an empty one to be returned and we will do a couple
more empty ones where we actually pass in something, we expect nothing to be returned.
And if they passed in the first parameter, we would also still expect nothing to be returned.
So more than we can do is we can actually do some simple ones.
So we can have a BCD.
We expect A to be returned here.
A B if we did B, we would expect B to be returned.
And lastly, if we did Core court DX and let's say we passed in four D, then we would expect RTI to
be returned and then let's do a couple more complicated ones.
We will say A, B, C, D, g, h, and we'll pass in a, d, f, r, and in this case we would expect
80 H to be returned and our last test case will do agg to AB.
So that way we have some repeating characters in here and we'll have gt x g t x a y b in which case
we would expect g tab to be returned.
So let's just double check this to make sure we are returning everything correctly so we have to be
g t a b, so we're looking for a t h.
We have add h at h t y.
So yeah, so everything looks pretty good here.
So let's run our test cases and see what we get.
And everything is passing successfully.
So we successfully implemented in our dynamic our, our dynamic programming solution to the longest
common sub sequence.
And hopefully this made sense to you again, with it being dynamic programming, sometimes it does add
an extra little layer of abstraction and my opinions and complexity to it.
So if you have any questions about my solution or the algorithm in general or just dynamic programming
in general, please feel free to ask them.
And the Q&A section.
And in the next lecture we will look at one more dynamic programming solution.
But before we move on to our next data structure.