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.

