1 00:00:06,600 --> 00:00:13,560 In this lecture, we are now going to go over the implementation to the longest common subsequent that 2 00:00:13,560 --> 00:00:15,570 we discussed in the previous lecture. 3 00:00:15,840 --> 00:00:25,950 So we're going to start off with the function initialization longest common sub C quints. 4 00:00:26,010 --> 00:00:29,610 And remember, we want to string. 5 00:00:29,610 --> 00:00:39,810 So we'll do two string slices and we want to return a string with our longest common subsequent given 6 00:00:39,810 --> 00:00:40,470 to us. 7 00:00:41,100 --> 00:00:46,650 So we want to store all the characters into a vector. 8 00:00:46,650 --> 00:00:58,770 So for us to do that, we can say let a vector of type char equal a dot charge dot collect. 9 00:00:58,770 --> 00:01:07,110 So now we just stored all of our A's into a vector and we want to do the same for B. 10 00:01:10,320 --> 00:01:19,680 And so here we are storing all the characters into the vector. 11 00:01:23,370 --> 00:01:34,260 Next, we want to store the lengths of our vectors so we can easily create it by saying let length A 12 00:01:34,260 --> 00:01:43,030 and link B equal to a dot lynne and B dot lynne. 13 00:01:44,580 --> 00:01:47,040 So we want to store the links. 14 00:01:48,960 --> 00:01:56,100 And then lastly or not lastly, next we want to say the solution is from within. 15 00:01:56,100 --> 00:02:09,630 I j is the length of the LCS say lcs longest common sub sequence 16 00:02:12,510 --> 00:02:29,700 and then between a of zero to I minus one and B from zero to J minus one. 17 00:02:31,110 --> 00:02:41,310 So for us to create this solutions vector that we want here, we need to use the links that we generated 18 00:02:41,310 --> 00:02:41,910 here. 19 00:02:43,230 --> 00:02:47,100 So we want the solution 20 00:02:50,070 --> 00:03:01,290 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 21 00:03:01,290 --> 00:03:02,010 one, 22 00:03:05,130 --> 00:03:16,680 and our other vector will be from zero to link a plus one. 23 00:03:16,950 --> 00:03:22,740 And I realized that I need to put those there. 24 00:03:22,740 --> 00:03:25,130 And let me add that there. 25 00:03:25,140 --> 00:03:25,680 All right. 26 00:03:25,680 --> 00:03:42,030 So we just created our solutions vector of links of a from 0 to 1 J minus one and zero to J minus one. 27 00:03:44,130 --> 00:03:51,330 All right, so now we can begin traversing our to DX array from top to bottom. 28 00:03:51,330 --> 00:03:56,520 So we want to enumerate all of our possibilities for that. 29 00:03:56,700 --> 00:04:00,540 So we will say for I of AI. 30 00:04:00,570 --> 00:04:07,800 So we want to iterate here and a dot editor and then remember we want to enumerate. 31 00:04:07,800 --> 00:04:14,700 So luckily Russ gives that to us, so we want to enumerate all the possibilities. 32 00:04:14,700 --> 00:04:24,990 And then for J and M of J and we want to do it the same thing for B, so. 33 00:04:25,020 --> 00:04:28,740 Editor dot enumerate. 34 00:04:29,820 --> 00:04:32,760 So now we're beginning to traverse down. 35 00:04:32,880 --> 00:04:43,470 So if M of I is equal to m of J, there is a new common character. 36 00:04:45,510 --> 00:04:51,870 Otherwise, take the best of the two solutions 37 00:04:53,970 --> 00:05:04,650 at I minus one to j and I to J. 38 00:05:04,890 --> 00:05:05,790 Minus one. 39 00:05:06,720 --> 00:05:07,470 So otherwise. 40 00:05:07,500 --> 00:05:11,020 So if M of a is equal to m of J, there is a new common character. 41 00:05:11,040 --> 00:05:19,980 Otherwise, take the best of the two solutions at I minus one and J and I of J minus one. 42 00:05:20,970 --> 00:05:29,220 So we can very quickly implement this by saying solutions of I plus one and J plus one. 43 00:05:29,520 --> 00:05:37,410 So we're just moving our index in the array equals if I equals of M of J. 44 00:05:37,590 --> 00:05:43,800 So if the solutions are the same or excuse me, if the characters are the same, then we want to say 45 00:05:43,800 --> 00:05:44,820 solutions. 46 00:05:46,590 --> 00:05:49,470 I keep saying solutions solution. 47 00:05:52,260 --> 00:05:57,120 I j plus one. 48 00:05:57,120 --> 00:06:02,640 So we are denoting it that we have a common character by putting the one value there. 49 00:06:05,580 --> 00:06:26,370 So now we say solutions solution of I and now we go j plus one dot max solution I plus one and J And 50 00:06:26,730 --> 00:06:35,190 this max method here that is given to us inside of the vector class is going to compare and return the 51 00:06:35,190 --> 00:06:36,750 maximum two values. 52 00:06:36,750 --> 00:06:44,400 So we're going to compare I and J plus one to solution of I plus one and J. 53 00:06:44,400 --> 00:06:48,270 So now we just implement it in this portion of it. 54 00:06:50,250 --> 00:06:59,460 And so once we've done all that well, then we have completely enumerated our to DX array from top left 55 00:06:59,460 --> 00:07:04,700 to bottom right or basically what we did in the previous lecture. 56 00:07:04,710 --> 00:07:08,190 So now we want to go from the bottom up. 57 00:07:08,190 --> 00:07:12,780 So we want to reconstitute the solution string. 58 00:07:12,780 --> 00:07:17,970 So we want to get our solution string back from the links. 59 00:07:19,080 --> 00:07:23,640 So if remember, if the value is one, then that means we had a common character. 60 00:07:24,240 --> 00:07:32,230 And so we want to take that character and add it into our our solution string, if you will. 61 00:07:32,250 --> 00:07:37,890 So to do this, we'll say let result of a vector type char 62 00:07:40,320 --> 00:07:57,420 equals a new vec and we'll say let mute I and mute J equals to length A and length B. 63 00:07:59,280 --> 00:08:13,200 So while I is greater than zero and J is greater than zero, we want to traverse from the bottom up. 64 00:08:13,200 --> 00:08:25,770 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 65 00:08:25,770 --> 00:08:28,260 because that means we have a common character. 66 00:08:28,260 --> 00:08:35,970 So we will say push a of I minus one and now we want to traverse up the array. 67 00:08:35,970 --> 00:08:38,820 So we're going to increment that way. 68 00:08:38,820 --> 00:08:43,620 We go back up to the top else if 69 00:08:46,530 --> 00:09:05,790 solution of I minus one and J is greater than solution of I and J minus one, then we just want to move 70 00:09:05,790 --> 00:09:07,800 up the AI value 71 00:09:10,770 --> 00:09:11,760 else. 72 00:09:11,910 --> 00:09:16,680 Our last case, we just want to move up the j value. 73 00:09:16,860 --> 00:09:26,700 So if they match, move up and increment both of them, if I minus one and J if this index is greater 74 00:09:26,700 --> 00:09:34,290 than this index, then we just increment I otherwise decrement J So again, that is just us traversing 75 00:09:34,290 --> 00:09:38,790 back up from the bottom to the top of our to DX array. 76 00:09:38,790 --> 00:09:42,600 And then as I said, I always like to reverse my string. 77 00:09:42,720 --> 00:09:48,780 That way it's back in kind of the order in which the string was presented to us and then for us to turn 78 00:09:48,780 --> 00:09:55,410 it into our string, we will say result that enter and collect. 79 00:09:56,730 --> 00:09:59,070 And I believe that is all we have to do. 80 00:09:59,070 --> 00:10:01,560 So let me do a cargo bill just to make sure that it runs. 81 00:10:01,560 --> 00:10:03,510 It looks like we're missing something. 82 00:10:04,720 --> 00:10:05,980 What are we missing? 83 00:10:06,280 --> 00:10:07,480 Get rid of that. 84 00:10:07,750 --> 00:10:10,000 That way it is actually returned. 85 00:10:10,360 --> 00:10:16,180 And line 45, I need to add our semicolon. 86 00:10:16,990 --> 00:10:17,950 How about now? 87 00:10:18,160 --> 00:10:19,130 Now we're happy. 88 00:10:19,150 --> 00:10:27,880 All right, so let's add in our test cases now to verify that our LCS function works. 89 00:10:28,690 --> 00:10:33,340 And we'll add in a couple of test cases to kind of vet it. 90 00:10:33,340 --> 00:10:34,030 Very good. 91 00:10:34,030 --> 00:10:36,520 So long as common, subsequent. 92 00:10:36,970 --> 00:10:41,530 And so we'll have an empty test case. 93 00:10:41,650 --> 00:10:48,310 So we will assert equals on our longest common subsequent. 94 00:10:48,310 --> 00:10:59,290 So if they pass in two empty strings, then we expect an empty one to be returned and we will do a couple 95 00:10:59,290 --> 00:11:06,850 more empty ones where we actually pass in something, we expect nothing to be returned. 96 00:11:06,850 --> 00:11:14,200 And if they passed in the first parameter, we would also still expect nothing to be returned. 97 00:11:16,000 --> 00:11:19,300 So more than we can do is we can actually do some simple ones. 98 00:11:19,300 --> 00:11:21,190 So we can have a BCD. 99 00:11:21,220 --> 00:11:24,130 We expect A to be returned here. 100 00:11:25,390 --> 00:11:32,140 A B if we did B, we would expect B to be returned. 101 00:11:34,210 --> 00:11:45,730 And lastly, if we did Core court DX and let's say we passed in four D, then we would expect RTI to 102 00:11:45,730 --> 00:11:50,920 be returned and then let's do a couple more complicated ones. 103 00:11:50,920 --> 00:12:04,000 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 104 00:12:04,000 --> 00:12:12,190 80 H to be returned and our last test case will do agg to AB. 105 00:12:12,220 --> 00:12:23,200 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 106 00:12:23,200 --> 00:12:27,700 we would expect g tab to be returned. 107 00:12:29,680 --> 00:12:34,850 So let's just double check this to make sure we are returning everything correctly so we have to be 108 00:12:34,900 --> 00:12:38,350 g t a b, so we're looking for a t h. 109 00:12:38,350 --> 00:12:41,860 We have add h at h t y. 110 00:12:41,860 --> 00:12:44,200 So yeah, so everything looks pretty good here. 111 00:12:44,320 --> 00:12:47,350 So let's run our test cases and see what we get. 112 00:12:47,350 --> 00:12:50,320 And everything is passing successfully. 113 00:12:51,040 --> 00:12:58,870 So we successfully implemented in our dynamic our, our dynamic programming solution to the longest 114 00:12:58,870 --> 00:13:00,460 common sub sequence. 115 00:13:00,610 --> 00:13:08,320 And hopefully this made sense to you again, with it being dynamic programming, sometimes it does add 116 00:13:08,320 --> 00:13:13,060 an extra little layer of abstraction and my opinions and complexity to it. 117 00:13:13,960 --> 00:13:21,970 So if you have any questions about my solution or the algorithm in general or just dynamic programming 118 00:13:21,970 --> 00:13:24,310 in general, please feel free to ask them. 119 00:13:24,310 --> 00:13:25,960 And the Q&A section. 120 00:13:25,960 --> 00:13:31,390 And in the next lecture we will look at one more dynamic programming solution. 121 00:13:31,390 --> 00:13:35,170 But before we move on to our next data structure.