1
00:00:00,230 --> 00:00:02,120
Hey there and welcome back.

2
00:00:02,150 --> 00:00:06,830
Let's now discuss a slightly better approach for solving this question.

3
00:00:06,830 --> 00:00:12,260
And because this is going to be a different approach or a way of solving DP problems that we have not

4
00:00:12,260 --> 00:00:19,250
previously discussed, we'll follow the procedure of first writing the recursive solution, and then

5
00:00:19,250 --> 00:00:20,930
we'll go ahead and memorize this.

6
00:00:20,930 --> 00:00:25,910
And after we are done with this we will discuss the tabulation approach as well.

7
00:00:25,910 --> 00:00:30,350
So let's get started now for coming up with the recursive solution.

8
00:00:30,350 --> 00:00:36,890
Let's try to make a few interesting observations and build the necessary intuition first.

9
00:00:36,890 --> 00:00:43,760
For this, let's take the example where the string given to us is hot spot and the word dictionary has

10
00:00:43,760 --> 00:00:46,100
two words hot and spot.

11
00:00:46,100 --> 00:00:50,360
Okay, now let me write the indices of these characters over here.

12
00:00:50,360 --> 00:00:54,020
So we have zero, one, two, three, four, five and six.

13
00:00:54,020 --> 00:00:57,980
Now the string which is given to us is hot spot.

14
00:00:57,980 --> 00:01:05,420
And let's say that we have a pointer over here, which is at the last character in the string which

15
00:01:05,420 --> 00:01:06,230
is given to us.

16
00:01:06,230 --> 00:01:13,940
Now let's say that this scenario where the pointer over here is pointing at this character, indicates

17
00:01:13,940 --> 00:01:22,130
the scenario where we are considering the substring that starts at h and goes up to the character t,

18
00:01:22,130 --> 00:01:25,670
okay, which is in this case hot spot or the complete string.

19
00:01:25,670 --> 00:01:26,090
All right.

20
00:01:26,090 --> 00:01:28,790
So we have established that we have a pointer.

21
00:01:28,790 --> 00:01:36,050
And the scenario where the pointer is over here represents the case where we are considering the substring

22
00:01:36,050 --> 00:01:40,820
that starts over here and goes right till this character okay.

23
00:01:40,820 --> 00:01:50,000
Now if this scenario has to give us the output as true, we know that that would mean that the entire

24
00:01:50,000 --> 00:01:56,720
string over here, or the string that starts at H and goes up to T, can be made from words in the word

25
00:01:56,720 --> 00:01:57,290
dictionary.

26
00:01:57,290 --> 00:01:57,710
Okay.

27
00:01:57,710 --> 00:02:06,830
So if that is the case, it would mean that there is a word in the given word dictionary that ends at

28
00:02:06,830 --> 00:02:10,370
the character at this particular index, which is t.

29
00:02:10,370 --> 00:02:10,700
Okay.

30
00:02:10,700 --> 00:02:16,250
So there should be a word in word dictionary that ends with the character t.

31
00:02:16,280 --> 00:02:21,200
Only then it's possible that this over here this scenario would return true.

32
00:02:21,200 --> 00:02:23,690
Okay, so let's make some space over here.

33
00:02:23,690 --> 00:02:31,130
And to check whether this is the case, we would have a for loop where we consider every word in the

34
00:02:31,130 --> 00:02:33,470
given word dictionary one at a time.

35
00:02:33,470 --> 00:02:36,830
And every word has a particular length.

36
00:02:37,130 --> 00:02:37,670
Okay.

37
00:02:37,670 --> 00:02:46,460
And we will check whether the substring that can be formed starting at index I minus length of the word

38
00:02:46,460 --> 00:02:47,330
plus one.

39
00:02:49,280 --> 00:02:50,480
Till index I.

40
00:02:50,510 --> 00:02:50,840
Okay.

41
00:02:50,840 --> 00:02:52,250
So that's what we have over here.

42
00:02:52,250 --> 00:02:57,860
If this is index I then if we subtract the length of the word from I.

43
00:02:57,890 --> 00:03:01,790
For example, let's say we got the word spot which has length four.

44
00:03:01,790 --> 00:03:06,530
So over here I is at index 0123456.

45
00:03:06,530 --> 00:03:10,430
So when we do six minus four that's equal to two.

46
00:03:10,430 --> 00:03:11,900
And that's over here right.

47
00:03:11,900 --> 00:03:13,490
So 012.

48
00:03:13,490 --> 00:03:19,880
And if you do I minus length of the word plus one will come to this particular index which is three.

49
00:03:19,880 --> 00:03:20,330
Okay.

50
00:03:20,330 --> 00:03:24,770
So what we discussed over here is we are going to take every word one word at a time.

51
00:03:24,770 --> 00:03:31,400
And we're going to check whether the substring that can be formed from index I minus length of the word

52
00:03:31,400 --> 00:03:35,030
plus one to I is in the word dictionary or not.

53
00:03:35,030 --> 00:03:37,730
And again let's quickly run over this once more.

54
00:03:37,730 --> 00:03:41,000
So initially let's say we are considering the word hot okay.

55
00:03:41,000 --> 00:03:47,030
And the length of this word is three and I is over here which is at index six.

56
00:03:47,030 --> 00:03:47,420
Okay.

57
00:03:47,420 --> 00:03:50,000
So 0123456.

58
00:03:50,000 --> 00:03:56,000
And over here when we are considering six minus three plus one that's equal to four.

59
00:03:56,000 --> 00:04:01,460
So we are considering the substring that goes from index four up to six okay.

60
00:04:01,460 --> 00:04:05,030
And that's POT456.

61
00:04:05,030 --> 00:04:05,330
Right.

62
00:04:05,330 --> 00:04:09,050
So we're going to check whether p o t is in the word dictionary.

63
00:04:09,050 --> 00:04:10,700
And we see that it's not.

64
00:04:10,700 --> 00:04:15,080
Therefore we proceed to the next word which is spot okay.

65
00:04:15,080 --> 00:04:18,890
And again I is at index six and six minus four.

66
00:04:18,920 --> 00:04:20,300
The length of this word is four.

67
00:04:20,300 --> 00:04:22,970
So six minus four plus one gives us three.

68
00:04:22,970 --> 00:04:25,250
That's this over here this index.

69
00:04:25,250 --> 00:04:30,620
And then we are considering the substring that goes from index three up to six which is spot.

70
00:04:30,620 --> 00:04:33,830
And we see that spot is there in the word dictionary.

71
00:04:33,830 --> 00:04:40,460
And therefore yes probably it could be that we are able to make this whole substring using words from

72
00:04:40,460 --> 00:04:41,120
the word dictionary.

73
00:04:41,120 --> 00:04:42,290
But more of that later.

74
00:04:42,290 --> 00:04:43,700
So this is the first step.

75
00:04:43,700 --> 00:04:45,950
We're trying to go over every word.

76
00:04:45,950 --> 00:04:54,710
And we're going to see whether we can form a word in word dictionary using few of the last characters

77
00:04:54,710 --> 00:04:56,090
in the given string.

78
00:04:56,330 --> 00:04:58,190
Now let's make some space over here.

79
00:04:58,190 --> 00:05:02,120
Now let's say for doing this, we have a particular function.

80
00:05:02,120 --> 00:05:06,110
And we are passing this particular index to the function over here.

81
00:05:06,110 --> 00:05:08,000
And you can name it as you wish.

82
00:05:08,000 --> 00:05:13,940
Now once we see that this is true, let's say we got spot and we saw that that's true.

83
00:05:14,300 --> 00:05:20,630
What remains to be checked is whether the remaining part in the string can also be formed using words

84
00:05:20,630 --> 00:05:21,860
in the word dictionary.

85
00:05:21,860 --> 00:05:26,240
And for that we would need to identify this particular index.

86
00:05:26,240 --> 00:05:26,660
Again.

87
00:05:26,660 --> 00:05:30,260
Notice we had I over here which was the last index of spot.

88
00:05:30,260 --> 00:05:32,120
And the remaining part is hot.

89
00:05:32,120 --> 00:05:39,170
So again we would need to identify this particular index which would be I minus length of the word.

90
00:05:39,170 --> 00:05:45,500
Again notice I was six over here and the length of this word is four and six minus four gives us two

91
00:05:45,530 --> 00:05:48,260
which is the index of this particular character okay.

92
00:05:48,260 --> 00:05:53,000
So this character would be at index I minus length of the word.

93
00:05:53,000 --> 00:05:56,810
And then we would just pass this particular index.

94
00:05:57,430 --> 00:06:01,060
To the same function that we called over here.

95
00:06:01,090 --> 00:06:01,510
Okay.

96
00:06:01,510 --> 00:06:07,690
So that would be step number two, which is that we will call the same function with the input parameter

97
00:06:07,690 --> 00:06:10,180
as I minus length of the word.

98
00:06:10,180 --> 00:06:17,320
And for us to be able to form the whole string which is given to us using words in word dictionary such

99
00:06:17,320 --> 00:06:22,390
that we make this part one particular word, which is what we have done so far.

100
00:06:22,390 --> 00:06:29,230
For that to be true, this part also should return true, or this particular call to the same function

101
00:06:29,230 --> 00:06:31,270
should also return true.

102
00:06:31,480 --> 00:06:36,460
Okay, so this is the approach that we are going to take for the recursive way of solving this question.

103
00:06:36,460 --> 00:06:42,130
And remember any recursive solution has a base case as well as a recursive case.

104
00:06:42,130 --> 00:06:48,970
So we have discussed over here the recursive case which is we start at this index and we try to identify

105
00:06:48,970 --> 00:06:55,720
whether there is a word in word dictionary such that this character becomes the last character in one

106
00:06:55,720 --> 00:06:57,130
of the words in our dictionary.

107
00:06:57,130 --> 00:07:03,220
And for example, over here we saw that yes, that's possible if we take the word spot, which is there

108
00:07:03,220 --> 00:07:08,680
in the word dictionary, and then we identify this index which is I minus length of that particular

109
00:07:08,680 --> 00:07:11,680
word, and we recursively call the same function again.

110
00:07:11,680 --> 00:07:13,390
So this is the recursive case.

111
00:07:13,390 --> 00:07:15,160
Now what about the base case.

112
00:07:15,160 --> 00:07:22,360
The base case would be if the index is less than zero then we would just return true okay.

113
00:07:22,360 --> 00:07:26,560
And again remember the base case can be thought of as the first invalid case.

114
00:07:26,560 --> 00:07:30,880
And an index which is less than zero is an invalid case okay.

115
00:07:30,880 --> 00:07:32,890
An index up to zero is valid.

116
00:07:32,890 --> 00:07:38,110
And when you get an index for the first time which is less than zero, that's the first invalid case

117
00:07:38,110 --> 00:07:39,190
that you have encountered.

118
00:07:39,190 --> 00:07:41,680
And we can use that as the base case.

119
00:07:41,680 --> 00:07:46,360
Now if we encounter the base case, we can just return true.

120
00:07:46,360 --> 00:07:48,520
And you can think of this in two ways.

121
00:07:48,520 --> 00:07:55,390
The first way of thinking about this, to understand why we can return true, is that if you are just

122
00:07:55,390 --> 00:08:01,330
given an empty string, you can just do nothing and you have formed that string right now.

123
00:08:01,330 --> 00:08:06,160
A better way, probably, to think of this would be let's say you're given the string hot.

124
00:08:06,160 --> 00:08:06,760
Okay.

125
00:08:06,760 --> 00:08:11,650
And let's say you have a word dictionary which has hot and a few other words.

126
00:08:11,650 --> 00:08:18,100
Now again you start at this index and you identify that there is a word in the word dictionary hot.

127
00:08:18,100 --> 00:08:24,670
And therefore you go ahead and try to find I minus length of the word, which is what we did over here.

128
00:08:24,670 --> 00:08:26,770
Okay, I minus length of the word.

129
00:08:26,770 --> 00:08:30,040
So when you do that you will come over here okay.

130
00:08:30,040 --> 00:08:31,240
That's what happened over here.

131
00:08:31,240 --> 00:08:31,480
Right.

132
00:08:31,480 --> 00:08:37,270
So we started at T and when we did I minus length of the word we came to this position okay.

133
00:08:37,270 --> 00:08:39,550
And in this case it was a valid index.

134
00:08:39,550 --> 00:08:43,630
But over here when you do that you will get an index which is less than zero.

135
00:08:43,630 --> 00:08:51,400
And in that case, logically we can return true because we were able to form the entire given string

136
00:08:51,520 --> 00:08:55,090
using words in word dictionary, which is hot in this case.

137
00:08:55,090 --> 00:09:00,160
Okay, so that's why if I is less than zero, that would be the base case.

138
00:09:00,160 --> 00:09:03,820
And if we hit the base case we will just return true.

139
00:09:03,820 --> 00:09:07,390
So this is the recursive approach for solving this question.

140
00:09:07,390 --> 00:09:09,760
Now let's go ahead and memoize this.

141
00:09:09,760 --> 00:09:11,410
Now memoization.

142
00:09:11,410 --> 00:09:15,850
After you are done with writing, the recursive solution is pretty straightforward.

143
00:09:15,850 --> 00:09:18,880
As you have seen in the previous questions that we have discussed.

144
00:09:18,880 --> 00:09:22,390
So you just need to store what you compute.

145
00:09:22,390 --> 00:09:27,430
And then before you go ahead and compute something, you have to check whether you have already computed

146
00:09:27,430 --> 00:09:28,810
this previously or not.

147
00:09:28,810 --> 00:09:30,730
So that's all about memoization right?

148
00:09:30,730 --> 00:09:34,390
So let's say again hotspot is the string which is given to us.

149
00:09:34,390 --> 00:09:39,730
Now for memorizing the solution we will need a DP array which will have n cells okay.

150
00:09:39,730 --> 00:09:42,040
So this is going to be the DP array that we have.

151
00:09:42,040 --> 00:09:47,020
And then at every index we will either store the value true or false.

152
00:09:47,020 --> 00:09:54,370
For example this cell over here represents whether this substring which starts at h and goes up to O,

153
00:09:54,370 --> 00:09:57,370
can be formed using words from the word dictionary.

154
00:09:57,370 --> 00:09:58,570
In a similar manner.

155
00:09:58,570 --> 00:10:05,590
This cell over here represents whether the substring that starts at h and goes up to p, which is hot

156
00:10:05,590 --> 00:10:09,280
soup, can be formed using words in the word dictionary or not.

157
00:10:09,280 --> 00:10:16,900
Similarly, this cell over here represents whether hot spot the entire string can be formed using words

158
00:10:16,900 --> 00:10:18,610
in word dictionary or not.

159
00:10:18,610 --> 00:10:21,010
So this is how we are going to solve this question.

160
00:10:21,010 --> 00:10:24,340
And notice this is just the recursive approach itself.

161
00:10:24,340 --> 00:10:28,000
And the only difference is that we are storing things that we compute.

162
00:10:28,000 --> 00:10:33,280
For example, again we start over here and we're going to check all the words in word dictionary to

163
00:10:33,280 --> 00:10:35,470
identify a word that ends in t.

164
00:10:35,470 --> 00:10:38,050
And we'll see that we have spot okay.

165
00:10:38,050 --> 00:10:41,680
We'll identify that this word indeed is there in word dictionary.

166
00:10:41,680 --> 00:10:45,970
And then we'll get to this character which is I minus length of the word.

167
00:10:45,970 --> 00:10:51,760
And we will check whether there is a word in word dictionary that ends with t.

168
00:10:51,760 --> 00:10:56,950
And we'll identify hot and we'll see that yes, indeed this part over here can be formed in.

169
00:10:57,110 --> 00:10:59,030
Read using words in our dictionary.

170
00:10:59,060 --> 00:10:59,720
Okay.

171
00:10:59,720 --> 00:11:07,280
And then when we go to I minus length of the word for this case we'll hit the base case because at this

172
00:11:07,280 --> 00:11:08,900
point I would be less than zero.

173
00:11:08,900 --> 00:11:12,770
And in this manner we will first fill through over here okay.

174
00:11:12,770 --> 00:11:17,990
And then using this true we will identify that this also can be filled as true.

175
00:11:17,990 --> 00:11:19,670
And that's how we solve this question.

176
00:11:19,670 --> 00:11:22,940
So this is the memorization approach for solving this question.

177
00:11:22,940 --> 00:11:29,090
Now you may have a question in your mind are there overlapping subproblems over here or not.

178
00:11:29,090 --> 00:11:34,940
Because as we have discussed previously, memoization is a dynamic programming technique which is to

179
00:11:34,940 --> 00:11:37,550
be used when there are overlapping subproblems.

180
00:11:37,550 --> 00:11:44,060
But probably you may feel that when you take a look at this question, there are no overlapping subproblems

181
00:11:44,060 --> 00:11:45,050
right now.

182
00:11:45,050 --> 00:11:52,520
To clarify this doubt, let's take another example to make overlapping subproblems very, very clear

183
00:11:52,520 --> 00:11:52,940
okay.

184
00:11:52,940 --> 00:12:01,340
So let's say the string which is given to us is this string over here, which is b b b b b a b b b b

185
00:12:01,340 --> 00:12:01,670
b.

186
00:12:01,670 --> 00:12:02,120
Okay.

187
00:12:02,120 --> 00:12:08,150
And let's say the word dictionary has these three words b b b and b b b.

188
00:12:08,270 --> 00:12:08,960
Okay.

189
00:12:08,960 --> 00:12:11,780
Now let's go ahead and write the indices over here.

190
00:12:11,780 --> 00:12:15,290
So we have zero, 123 etc. up to ten.

191
00:12:15,290 --> 00:12:18,710
And initially we are going to start over here okay.

192
00:12:18,710 --> 00:12:22,040
So we will be calling the function that we will write.

193
00:12:22,040 --> 00:12:24,830
And the input parameter would be ten okay.

194
00:12:24,830 --> 00:12:30,200
And at this point we will see that there is a word b b b okay.

195
00:12:30,200 --> 00:12:32,540
Let's say we first take a look at this word.

196
00:12:32,540 --> 00:12:33,020
Again.

197
00:12:33,020 --> 00:12:36,620
It depends on how we go through the words in word dictionary.

198
00:12:36,650 --> 00:12:40,130
Now you can imagine that let's say this is the first word in word dictionary.

199
00:12:40,130 --> 00:12:45,920
And because we get a match we identify I minus length of the word which is three.

200
00:12:45,920 --> 00:12:48,050
So ten minus three gives us seven okay.

201
00:12:48,050 --> 00:12:51,170
So we are over here and we make this call f of seven.

202
00:12:51,170 --> 00:12:56,810
And at this point let's say we see this word in the dictionary and we see a match.

203
00:12:56,810 --> 00:12:58,520
And therefore we come over here.

204
00:12:59,410 --> 00:12:59,860
Okay.

205
00:12:59,860 --> 00:13:08,620
And that's F5 and EF5, which is over here will return false because there is no word in word dictionary

206
00:13:08,620 --> 00:13:11,830
ending with an A, so we'll not get any match over here.

207
00:13:11,830 --> 00:13:14,140
And for that reason this will return false.

208
00:13:14,140 --> 00:13:16,990
And therefore F of seven also will return false.

209
00:13:16,990 --> 00:13:19,990
And then f of ten will try another combination.

210
00:13:19,990 --> 00:13:20,410
Okay.

211
00:13:20,410 --> 00:13:23,860
So let's say it at this point sees that there is B.

212
00:13:25,520 --> 00:13:29,270
So F of ten will call F of eight.

213
00:13:29,630 --> 00:13:30,320
Okay.

214
00:13:30,320 --> 00:13:31,790
And f of eight.

215
00:13:31,790 --> 00:13:33,950
Let's say it's seeing this b.

216
00:13:33,950 --> 00:13:36,650
So it identifies a match over here.

217
00:13:36,650 --> 00:13:40,010
And it calls F of seven which is what we have over here.

218
00:13:40,010 --> 00:13:44,030
And let's say at this point it identifies B as a match.

219
00:13:44,030 --> 00:13:47,390
And therefore f of seven calls f of five.

220
00:13:47,420 --> 00:13:48,050
Okay.

221
00:13:48,050 --> 00:13:49,280
And we reach over here.

222
00:13:49,280 --> 00:13:54,380
And at this point because you have an A over here and there is no word in our dictionary ending with

223
00:13:54,380 --> 00:13:57,080
an A, F of five will return false.

224
00:13:57,080 --> 00:14:01,490
And therefore f of seven will return false and f of eight will return false.

225
00:14:01,490 --> 00:14:02,690
And it goes on in this manner.

226
00:14:02,690 --> 00:14:03,140
Okay.

227
00:14:03,140 --> 00:14:09,290
But again our aim is to just identify that there are overlapping subproblems in this question.

228
00:14:09,290 --> 00:14:10,760
And again now it's very clear.

229
00:14:10,760 --> 00:14:11,030
Right.

230
00:14:11,030 --> 00:14:14,750
You have F of five over here and you have F of five over here.

231
00:14:14,750 --> 00:14:16,460
You have f of seven over here.

232
00:14:16,460 --> 00:14:18,110
And you have f of seven over here.

233
00:14:18,110 --> 00:14:19,280
And it goes on like that.

234
00:14:19,280 --> 00:14:19,790
Right.

235
00:14:19,790 --> 00:14:26,630
So in this example it's very clear that there are overlapping subproblems.

236
00:14:26,630 --> 00:14:33,260
And that's why using memoization helps us to get a much better time complexity.