1 00:00:00,930 --> 00:00:01,680 Hi, everyone. 2 00:00:01,710 --> 00:00:07,870 So in this video, we are going to solve this question at a distance, so what is the problem statement? 3 00:00:08,130 --> 00:00:15,360 So what we need to do so given two words, word one and word two, so we need to convert word one into 4 00:00:15,480 --> 00:00:20,220 word two and allow the operation is we can insert one character in word one. 5 00:00:20,220 --> 00:00:24,960 We can delete one character from word one, we can replace one character from word one. 6 00:00:25,590 --> 00:00:29,130 And our ultimate goal is to convert word one into word two. 7 00:00:29,520 --> 00:00:32,130 And we need to find out the minimum operations. 8 00:00:32,369 --> 00:00:32,790 Right. 9 00:00:33,300 --> 00:00:35,820 We need to find out the minimum number of operations. 10 00:00:35,820 --> 00:00:40,740 And these are the three operations that we have inserted character in word one, the little character 11 00:00:40,740 --> 00:00:43,210 from word one and replace the character from word one. 12 00:00:43,690 --> 00:00:44,850 Let's take one example. 13 00:00:44,860 --> 00:00:47,250 So I have this example. 14 00:00:47,550 --> 00:00:53,600 The word one is horse, and I want to convert this word into arrows. 15 00:00:54,060 --> 00:00:58,590 So the first step is basically replace it with R, so replace it with ah. 16 00:00:59,490 --> 00:01:07,330 Now this is Aurora SC second step stabilising remove R so remove or remove means delete the character. 17 00:01:07,680 --> 00:01:16,380 So now it becomes rwc and tardies basically again delete this character so null rules so it becomes 18 00:01:16,390 --> 00:01:18,120 it to the word two. 19 00:01:18,240 --> 00:01:19,920 So we three operations. 20 00:01:19,920 --> 00:01:20,280 Right. 21 00:01:20,550 --> 00:01:24,330 So we did the operation first is replaced and then to delete operations. 22 00:01:24,570 --> 00:01:26,850 So the number of operations that period is three. 23 00:01:26,860 --> 00:01:30,120 So that's why the answer for this input will be three. 24 00:01:30,360 --> 00:01:33,400 Let's take one more example and let's try to understand. 25 00:01:34,230 --> 00:01:40,170 So the second example that is given to us is basically we need to convert the word intention. 26 00:01:41,250 --> 00:01:44,520 We need to convert the word intention to execution. 27 00:01:46,830 --> 00:01:51,680 And the number of steps will be five, let's see what will be the step so far removed. 28 00:01:52,920 --> 00:01:58,230 So after removing B, this will be my strength, i n n d I own. 29 00:01:58,710 --> 00:02:07,980 The second is basically replace I with E, replace I with E, so this will be an NBA. 30 00:02:08,220 --> 00:02:18,780 And now the third is basically replace and with X, so replace and with X, X N D Io and then replace 31 00:02:18,780 --> 00:02:20,190 and with C.. 32 00:02:21,150 --> 00:02:27,640 So replace and we see it will become the new and the last is basically insert U. 33 00:02:28,680 --> 00:02:37,650 So we will insert you here and it will become x, e, c you PICU and which is a close to this word and 34 00:02:37,650 --> 00:02:39,150 with five operations. 35 00:02:39,420 --> 00:02:41,610 So that's why the output will be five. 36 00:02:41,920 --> 00:02:43,710 So I hope you have understood the question. 37 00:02:43,740 --> 00:02:46,340 Now let's see how we can solve this question. 38 00:02:46,620 --> 00:02:48,120 So it's pretty simple question. 39 00:02:48,120 --> 00:02:50,150 We can easily use recursion here. 40 00:02:51,270 --> 00:02:53,720 So how we will be able to use recursion. 41 00:02:53,730 --> 00:02:54,170 Let's see. 42 00:02:54,930 --> 00:03:00,930 So what we need to do, we need to convert word one into over two. 43 00:03:03,510 --> 00:03:08,850 And these are the three operations allowed, we can insert one character, we can insert one character, 44 00:03:08,850 --> 00:03:12,150 we can delete one character and we can replace one character. 45 00:03:13,200 --> 00:03:15,720 And we need to find out the minimum number of operations. 46 00:03:18,410 --> 00:03:23,830 So this is a pretty simple problem, but you need to do so, let's take this example only. 47 00:03:23,870 --> 00:03:31,710 Let's take I want to convert this word fruit into, let's say, this word for unity. 48 00:03:33,950 --> 00:03:40,520 So what you're gonna do is you will stand here, you'll compare the last character, will compare the 49 00:03:40,520 --> 00:03:41,330 last character. 50 00:03:41,360 --> 00:03:42,860 So the last character is same. 51 00:03:43,640 --> 00:03:47,990 So what I will do, I will tell Dacogen to solve this problem and this problem. 52 00:03:48,890 --> 00:03:49,220 Right. 53 00:03:49,510 --> 00:03:56,180 So, again, if there is match, if there is a match, then we do not need to do any of the operation 54 00:03:56,180 --> 00:03:58,310 because the characters are matching. 55 00:03:58,880 --> 00:04:04,790 So if there is a match, for example, the length of this string is basically let's m and the length 56 00:04:04,790 --> 00:04:11,060 of the string is basically let's say and then ready to do, we will call for M minus one and minus one 57 00:04:11,060 --> 00:04:14,600 to simply call recursion, let's say added distance. 58 00:04:15,260 --> 00:04:18,279 Let's say the name or the name of the function is minimum distance. 59 00:04:18,649 --> 00:04:25,370 So what I will do, I will call the function minimum distance, string one and a minus one, string 60 00:04:25,370 --> 00:04:27,140 two and and minus one. 61 00:04:27,140 --> 00:04:27,530 Right. 62 00:04:27,860 --> 00:04:29,060 Will pass this part. 63 00:04:30,680 --> 00:04:36,550 Now if there is no match, so let's see if this character is a different calculated. 64 00:04:36,620 --> 00:04:43,460 This character is now if matching is not there, the characters are not matching and they are different. 65 00:04:43,490 --> 00:04:49,680 Now we have three operations, so we have three operation insert, delete and replace. 66 00:04:50,060 --> 00:04:52,810 So what I will do, I will try to insert one character. 67 00:04:53,120 --> 00:05:00,980 So for insertion, if I want to insert what will be my record, because it will be empty medium distance 68 00:05:01,430 --> 00:05:08,900 string when M string two and minus one, this will be the insertion. 69 00:05:09,150 --> 00:05:11,060 What will be the deletion? 70 00:05:11,330 --> 00:05:13,900 The second option is I delete this character. 71 00:05:14,540 --> 00:05:17,210 So the first option is insert the character here. 72 00:05:17,240 --> 00:05:18,750 Second option is delete it. 73 00:05:19,190 --> 00:05:25,460 So for deleting E, this will be string one and minus one, I will call the question on and minus one 74 00:05:25,910 --> 00:05:27,380 string and it will be. 75 00:05:27,380 --> 00:05:37,570 And now the third option is to replace replace character with the so replaced in case of replace your 76 00:05:37,570 --> 00:05:41,680 recursion will be M minus one as two and minus one. 77 00:05:42,320 --> 00:05:46,350 So these three will be recursive call if you are not able to understand. 78 00:05:46,370 --> 00:05:50,120 Let me explain you again how these three will be directly Yancoal. 79 00:05:51,500 --> 00:05:53,900 Let me write that example once again. 80 00:05:57,430 --> 00:06:03,850 So the example was, you want to convert this world into this one. 81 00:06:06,190 --> 00:06:06,620 Right. 82 00:06:08,410 --> 00:06:11,660 So what I'm saying here is the last character is different. 83 00:06:12,100 --> 00:06:15,550 So this is a necessity since they are different. 84 00:06:15,970 --> 00:06:17,380 We have three options. 85 00:06:17,500 --> 00:06:23,460 Either we will insert so by insertion, but I will do I will insert the character here. 86 00:06:23,500 --> 00:06:28,170 So after inserting what I will do, I will call recursion like this. 87 00:06:28,750 --> 00:06:33,870 The second option is I can delete these characters, do not insert just delete this character. 88 00:06:34,930 --> 00:06:36,660 Then my reaction will look like this. 89 00:06:37,750 --> 00:06:39,810 The third option is basically simply replace. 90 00:06:39,820 --> 00:06:44,380 So instead of deleting E, you will simply replace it with T. 91 00:06:44,590 --> 00:06:47,450 If you are replacing with D then your next location will be like this. 92 00:06:49,150 --> 00:06:51,480 So that is, that will be a recursive call. 93 00:06:51,640 --> 00:06:55,580 And what we need to do, we need to find out the minimum of all of them. 94 00:06:55,630 --> 00:06:57,690 I have three option insert, delete and such. 95 00:06:58,000 --> 00:07:00,010 We need to return the minimum number of operation. 96 00:07:00,200 --> 00:07:05,410 So I will take the minimum of these three and I will add plus one because I am doing one operation. 97 00:07:05,410 --> 00:07:08,800 Right, that I'm inserting, that I am deleting or I am replacing. 98 00:07:09,010 --> 00:07:13,000 So I will add one plus minimum of these operations. 99 00:07:14,020 --> 00:07:15,060 So it's pretty simple. 100 00:07:15,400 --> 00:07:16,900 Directly jump into the code. 101 00:07:20,950 --> 00:07:22,960 So let's start writing the code. 102 00:07:26,190 --> 00:07:34,410 The name of the function is and minimum distance, what it will take, it will take one string as input 103 00:07:35,820 --> 00:07:42,570 and the size of that string string to as input and the size of the string. 104 00:07:43,860 --> 00:07:45,540 Now let's talk about the base case. 105 00:07:45,540 --> 00:07:51,930 First base case is if string one is empty, string one does not exist. 106 00:07:52,410 --> 00:07:56,580 So if string one, this does not exist and you want to convert string one interesting to, then you 107 00:07:56,580 --> 00:08:03,720 need to insert all the characters of string to and how many characters we need to insert the number 108 00:08:03,720 --> 00:08:06,570 of characters which are present in string to which is. 109 00:08:06,720 --> 00:08:09,060 And so I will return and. 110 00:08:11,580 --> 00:08:17,980 Second option is if the second string does not exist, so if the second string does not exist. 111 00:08:18,000 --> 00:08:21,090 Second string does not exist means empty. 112 00:08:21,300 --> 00:08:26,850 So if the second string is empty and you want to convert string one into an empty string, what are 113 00:08:26,850 --> 00:08:27,240 you to do? 114 00:08:27,250 --> 00:08:29,790 You know, to delete all the characters. 115 00:08:29,790 --> 00:08:33,650 President String, when and how many characters are there characters out there? 116 00:08:34,080 --> 00:08:35,600 So you will return. 117 00:08:35,610 --> 00:08:37,980 And so what I'm doing. 118 00:08:40,240 --> 00:08:48,760 So this will be so here what I am doing since Stringbean is empty, so you need to insert all the characters 119 00:08:48,760 --> 00:09:00,250 of a string to insert all characters of a string to and ahead of our time doing since string two does 120 00:09:00,250 --> 00:09:00,940 not exist. 121 00:09:00,940 --> 00:09:08,170 So we need to delete all characters from string ones or delete all characters of a string. 122 00:09:08,170 --> 00:09:09,550 When and how many characters are there. 123 00:09:09,820 --> 00:09:17,120 Characters are there the sizes m so that is the best case now if the characters are matching. 124 00:09:17,140 --> 00:09:27,180 So if as one of M minus one is equals to as 12, I am checking for the last character. 125 00:09:27,190 --> 00:09:35,110 So last, if the size is M then the last character index will be M minus one and similarly for the second 126 00:09:35,110 --> 00:09:35,390 string. 127 00:09:35,410 --> 00:09:42,910 So if the last character Rasim, if the last character assassin then do nothing, just called the recursion 128 00:09:42,910 --> 00:09:43,950 on the rest of the string. 129 00:09:45,220 --> 00:09:52,960 So we will not do anything, it will be just simply calling the equation on the rest of the string. 130 00:09:54,700 --> 00:09:58,080 Now if this is not the case then what to do. 131 00:09:58,400 --> 00:10:01,340 I would answer will be written. 132 00:10:01,420 --> 00:10:02,890 I have I have three option. 133 00:10:03,730 --> 00:10:04,690 I have three options. 134 00:10:04,740 --> 00:10:15,970 Either I will insert so far in such an empty string one as are discussed, this will be M this will 135 00:10:15,970 --> 00:10:18,370 be string two and this will be and minus one. 136 00:10:18,800 --> 00:10:21,270 This is the same call for the insertion. 137 00:10:22,030 --> 00:10:23,880 Second is delete the character. 138 00:10:25,270 --> 00:10:26,830 So this will be empty. 139 00:10:28,240 --> 00:10:33,580 String one minus one, string two and minus one. 140 00:10:34,420 --> 00:10:40,300 So at the end and the third option is replace the characters which are not matching. 141 00:10:41,380 --> 00:10:42,840 So this is for replace. 142 00:10:42,850 --> 00:10:45,250 This will be empty string when. 143 00:10:47,340 --> 00:10:50,920 And minus one, string two and minus one. 144 00:10:51,240 --> 00:10:55,100 So we are replacing the characters and what would be my answer? 145 00:10:55,950 --> 00:11:01,710 My answer will be I am doing one operation, either insert, either delete, either replace, so one 146 00:11:01,710 --> 00:11:12,720 operation plus the minimum of these insert comma, minimum of delete, comma, replace, and that will 147 00:11:12,720 --> 00:11:14,020 be the entire code. 148 00:11:14,490 --> 00:11:18,390 So if you are having confusion, let me write the full name here. 149 00:11:18,390 --> 00:11:19,590 I'm inserting the characters. 150 00:11:19,590 --> 00:11:20,220 Interesting one. 151 00:11:20,970 --> 00:11:27,090 Here I am deleting the character from string one and here I am replacing the characters of String one 152 00:11:27,090 --> 00:11:28,390 by a string to character. 153 00:11:29,310 --> 00:11:40,770 So this is insert name of insert delete and replace and plus one because we did one operation. 154 00:11:41,460 --> 00:11:43,300 So that will be the complete code. 155 00:11:43,320 --> 00:11:51,840 And here you will simply call this function return empty string when what is sorry, this is word one 156 00:11:54,300 --> 00:11:58,080 M so the site is basically word rendered size. 157 00:12:00,900 --> 00:12:05,130 Second is where to and where to start, says. 158 00:12:07,080 --> 00:12:10,050 So that's all, let's try to run our good. 159 00:12:14,570 --> 00:12:19,910 So basically, our code is working, let's try to submit our code, so it is very obvious that we are 160 00:12:19,910 --> 00:12:25,900 going to encounter a time limit extended because this is recursive solution. 161 00:12:26,270 --> 00:12:32,590 So basically we are getting time exited and that is because our solution is recursive. 162 00:12:32,630 --> 00:12:39,410 And so in the next we do what we are going to do is we will convert this recursive solution into DPN. 163 00:12:40,040 --> 00:12:43,130 We will modify this code and we will use dynamic programming here. 164 00:12:43,980 --> 00:12:44,420 Right. 165 00:12:45,020 --> 00:12:46,720 So this is all from this video. 166 00:12:46,730 --> 00:12:50,090 If you have any doubt, ask me in the Q&A section. 167 00:12:50,300 --> 00:12:52,070 I will be more than happy to help you out. 168 00:12:52,550 --> 00:12:54,500 So this is all from this video, guys. 169 00:12:54,540 --> 00:12:56,030 I will see you in the next one. 170 00:12:56,300 --> 00:12:56,840 Thank you.