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.

