1 00:00:00,960 --> 00:00:01,660 Hi, everyone. 2 00:00:01,680 --> 00:00:07,170 So in this video, we're going to do we are going to convert our exclusive called in to dynamic programming 3 00:00:07,170 --> 00:00:10,980 code because this exclusive code is giving us time limit exited. 4 00:00:11,340 --> 00:00:16,620 So we will use dynamic programming and let's see how we can use dynamic programming here. 5 00:00:20,870 --> 00:00:24,990 So we can easily convert this recursive call entertaining programming. 6 00:00:25,250 --> 00:00:30,070 So what I will do, I will create one tutelary because two strings are there. 7 00:00:31,370 --> 00:00:35,610 So I'm going to convert, I'm going to create this to create this. 8 00:00:36,860 --> 00:00:38,430 And I would answer with this one. 9 00:00:38,750 --> 00:00:48,350 So our answer is going to be DPF and and and what DEPI of IJI represent so deep of IJI represent the 10 00:00:48,350 --> 00:00:55,790 minimum distance minimum number of operations to convert Wordsworthian to work to by considering I correctors 11 00:00:56,330 --> 00:01:05,660 my concerting I characters of words, one that is string one and considering the characters of string 12 00:01:05,660 --> 00:01:05,930 two. 13 00:01:06,680 --> 00:01:08,390 So that is the meaning of. 14 00:01:10,430 --> 00:01:16,640 DPO Fidge celebrating myself, but DPO physically present DPF, I did at present the minimum number 15 00:01:16,640 --> 00:01:19,130 of operations to convert string one. 16 00:01:19,130 --> 00:01:24,380 Interesting to and considering I characters hosting and hosting when so going. 17 00:01:24,380 --> 00:01:29,540 By this definition, my answer will be DPF Emelin, which will be the minimum number of operations to 18 00:01:29,540 --> 00:01:30,350 convert Stenglein. 19 00:01:30,350 --> 00:01:36,410 Interesting to by considering M characters of String one and end characters of String two, basically 20 00:01:36,770 --> 00:01:42,050 by considering and digesting one and considering an entire string to write. 21 00:01:42,290 --> 00:01:48,560 And I will start from zero and this will be the indexing m similarly zero and this will be. 22 00:01:48,560 --> 00:01:50,390 And what will be the best case. 23 00:01:50,600 --> 00:01:53,930 Best case will be if the string one is empty. 24 00:01:54,380 --> 00:02:01,520 So if one is empty, how many operations will be required to convert string when adjusting to it will 25 00:02:01,520 --> 00:02:07,790 be basically the size of string two that will be zero, one, two, three and so on. 26 00:02:08,539 --> 00:02:13,430 Similarly, if the second string does not exist, what we need to do, we need to delete all the characters 27 00:02:13,430 --> 00:02:14,310 from string one. 28 00:02:14,600 --> 00:02:17,330 So again, 012 and so on. 29 00:02:17,840 --> 00:02:18,120 Right. 30 00:02:18,230 --> 00:02:19,490 This will be the best case. 31 00:02:20,570 --> 00:02:22,790 And this recursive is very simple. 32 00:02:23,240 --> 00:02:23,650 Right? 33 00:02:23,900 --> 00:02:26,090 So let's just start writing the code. 34 00:02:30,290 --> 00:02:36,710 So let me try it again for you, so what I'm trying to say here is my answer would be DPE of. 35 00:02:37,850 --> 00:02:44,000 M and and and the best case that I was talking about is so if. 36 00:02:45,890 --> 00:02:46,700 See if. 37 00:02:49,300 --> 00:02:57,200 Let's talk about this index, right, so the value of a zero string one does not exist and this is G 38 00:02:57,790 --> 00:02:58,070 rate. 39 00:02:58,390 --> 00:03:00,700 So what will be the value of IJI? 40 00:03:02,920 --> 00:03:09,380 The value of it will be first string is empty and second string is containing characters, right? 41 00:03:09,400 --> 00:03:10,450 The value of a zero. 42 00:03:10,990 --> 00:03:15,610 So first string is empty and the second string contains the character. 43 00:03:16,210 --> 00:03:19,000 So what I need to do to convert string went into string. 44 00:03:19,000 --> 00:03:24,010 Do you need to insert all the characters and how many characters are there? 45 00:03:24,370 --> 00:03:25,230 Characters are there. 46 00:03:25,540 --> 00:03:29,320 So this will be G so this will be G. 47 00:03:30,250 --> 00:03:31,350 I'm repeating myself. 48 00:03:31,360 --> 00:03:36,260 C first string is empty plate first string is empty. 49 00:03:36,280 --> 00:03:38,440 Second string is containing characters. 50 00:03:38,440 --> 00:03:40,470 I want to convert string when into string two. 51 00:03:40,690 --> 00:03:46,540 So the only solution is insert all the characters of string to interesting when and how many characters 52 00:03:46,540 --> 00:03:46,950 are there. 53 00:03:46,990 --> 00:03:48,400 String two characters are there. 54 00:03:48,610 --> 00:03:49,500 So that's Viji. 55 00:03:50,110 --> 00:03:51,760 And similarly the posit for this. 56 00:03:52,120 --> 00:03:58,470 If the value of JS zero and this is your IHI, then DP of IGY. 57 00:03:58,810 --> 00:04:01,270 So what is G JS basically zero. 58 00:04:01,480 --> 00:04:03,910 The second string string has two does not exist. 59 00:04:04,150 --> 00:04:05,620 So in this case, what to do. 60 00:04:05,620 --> 00:04:08,350 You need to delete all the characters from string one. 61 00:04:08,950 --> 00:04:11,740 And how many characters are there i.e. characters are there. 62 00:04:12,640 --> 00:04:15,220 So this will be, this index will be I. 63 00:04:15,940 --> 00:04:24,530 That's why I write here like this zero, one, two, three and so on til and and similarly 012 tell. 64 00:04:24,610 --> 00:04:26,440 And that's why I write this. 65 00:04:26,440 --> 00:04:26,760 Right. 66 00:04:27,040 --> 00:04:29,650 So let's start writing the code now. 67 00:04:31,120 --> 00:04:36,130 So the code is going to be very, very similar to the recursive when you are just converting your recursive 68 00:04:36,130 --> 00:04:37,600 solution into the solution. 69 00:04:37,600 --> 00:04:39,160 So that will be pretty simple. 70 00:04:39,580 --> 00:04:44,590 So what is M m is basically okay so let's first rename this too. 71 00:04:44,620 --> 00:04:49,420 String S1 and the second is string as two Saudi. 72 00:04:51,600 --> 00:04:59,670 The second is basically stating as to what is M m is basically a standard size. 73 00:05:02,290 --> 00:05:09,610 And what is and is basically string to that size now you are creating one deputy. 74 00:05:10,860 --> 00:05:15,690 The P5+1 and and blessin, because of Iran, said it will be the feminine. 75 00:05:18,210 --> 00:05:28,770 So our answer will be DEPI of em and and because of Ejeta percent, we have discussed what the payoff 76 00:05:28,770 --> 00:05:29,730 IJA represent. 77 00:05:31,290 --> 00:05:37,380 I'm telling you again, so deep off, IJA represent the minimum number of operations to convert a string 78 00:05:37,380 --> 00:05:43,260 one into string to by considering a character hosting one and considering the character hosting two. 79 00:05:45,030 --> 00:05:47,880 So according to this formula out on Will Bill Feminine. 80 00:05:50,240 --> 00:05:51,500 Now, what we need to do here. 81 00:05:52,860 --> 00:05:59,530 Just simply, I trade all this debris to family values, so I equals zero. 82 00:05:59,580 --> 00:06:01,200 I lost another close to em. 83 00:06:06,900 --> 00:06:13,920 Four and J equals zero G less than articles to n g placeless. 84 00:06:15,570 --> 00:06:23,700 Now, the best case that we were talking about, so if the first string is empty, then in that case 85 00:06:25,080 --> 00:06:30,420 you going to insert all the characters of second string and how many characters are there characters? 86 00:06:30,420 --> 00:06:33,540 Are there elusive? 87 00:06:35,760 --> 00:06:42,060 The second string is empty, so if the second string is empty, then you need to delete all the characters 88 00:06:42,090 --> 00:06:42,700 from string. 89 00:06:42,720 --> 00:06:44,180 When and how many characters are there? 90 00:06:44,190 --> 00:06:53,700 And when I characters out there in Stringbean in the elusive if there is a match, match means as one 91 00:06:53,700 --> 00:06:54,330 of I. 92 00:06:55,170 --> 00:06:57,590 Is it close to as two of G. 93 00:06:58,560 --> 00:06:59,340 This is wrong. 94 00:06:59,370 --> 00:07:06,960 I explained in our last video in the last problem that this will be minus one, so this will be minus 95 00:07:06,960 --> 00:07:07,190 one. 96 00:07:08,490 --> 00:07:13,140 So if that is the case, we can see so damaging. 97 00:07:13,140 --> 00:07:16,520 If they are matching then you simply along and minus and minus. 98 00:07:16,530 --> 00:07:18,550 And so that will be DPL. 99 00:07:18,570 --> 00:07:19,320 Vijay will be. 100 00:07:22,860 --> 00:07:27,280 Simple B of A, minus one and minus one. 101 00:07:29,100 --> 00:07:34,800 Now, in the old part, if there are if the characters are not matching, so if the characters are not 102 00:07:34,800 --> 00:07:38,620 matching, we have three operations, insert, delete and replace. 103 00:07:39,600 --> 00:07:47,970 So what will be insert, insert will be DBF, I and G minus one. 104 00:07:49,850 --> 00:08:00,140 What is the latest dip of a minus one and G and replace? 105 00:08:03,900 --> 00:08:11,700 So what is replacer place will really be of I minus one and G minus one, like we have discussed all 106 00:08:11,700 --> 00:08:14,100 this here I am doing exactly the same. 107 00:08:14,100 --> 00:08:14,450 Right. 108 00:08:15,720 --> 00:08:17,660 And finally, what will be my answer? 109 00:08:18,720 --> 00:08:21,660 What will be my answer to my answer will be when? 110 00:08:21,660 --> 00:08:24,650 Because we did it in the right place. 111 00:08:25,020 --> 00:08:28,410 So my answer will be one plus minimum of. 112 00:08:30,270 --> 00:08:30,930 Insert. 113 00:08:32,940 --> 00:08:39,730 Mean you move out of these three, you going to take minimum, because in the question they are asking 114 00:08:39,730 --> 00:08:43,390 us to report, our answer is the minimum number of operations required. 115 00:08:44,020 --> 00:08:44,830 So that does it. 116 00:08:44,950 --> 00:08:46,540 This will be you had an Paragould. 117 00:08:50,500 --> 00:08:57,130 Late, this will be our and bad cold, so let's first run this score and then we will submit. 118 00:09:00,620 --> 00:09:04,260 So our it is working fine now let's summit our goal. 119 00:09:06,080 --> 00:09:11,080 And since this is a deep solution, so this will not encounter anti-American. 120 00:09:11,120 --> 00:09:11,530 Yes. 121 00:09:11,540 --> 00:09:14,210 So our code has passed all the test cases. 122 00:09:14,210 --> 00:09:14,600 Right. 123 00:09:15,380 --> 00:09:18,440 And now what is the time and the space complexity? 124 00:09:18,770 --> 00:09:19,940 The time complexities. 125 00:09:19,940 --> 00:09:22,490 Basically big famine you are trading. 126 00:09:22,490 --> 00:09:22,880 Right. 127 00:09:23,390 --> 00:09:25,760 And the space complexities you created this. 128 00:09:25,760 --> 00:09:27,920 Deepti So space complexities. 129 00:09:27,920 --> 00:09:32,900 Amann So this is the time and the space complexity for this minimum distance problem. 130 00:09:33,750 --> 00:09:34,130 Right. 131 00:09:35,690 --> 00:09:39,730 And this is pretty much very, very simple and it goes on relationship. 132 00:09:40,880 --> 00:09:44,000 So if you have any doubt in this problem, do ask me. 133 00:09:44,660 --> 00:09:46,670 So this is all about this problem. 134 00:09:46,700 --> 00:09:48,170 I will see you in the next one. 135 00:09:48,530 --> 00:09:49,100 Thank you.