Hey there and welcome back.
Let's now discuss a slightly better approach for solving this question.
And because this is going to be a different approach or a way of solving DP problems that we have not
previously discussed, we'll follow the procedure of first writing the recursive solution, and then
we'll go ahead and memorize this.
And after we are done with this we will discuss the tabulation approach as well.
So let's get started now for coming up with the recursive solution.
Let's try to make a few interesting observations and build the necessary intuition first.
For this, let's take the example where the string given to us is hot spot and the word dictionary has
two words hot and spot.
Okay, now let me write the indices of these characters over here.
So we have zero, one, two, three, four, five and six.
Now the string which is given to us is hot spot.
And let's say that we have a pointer over here, which is at the last character in the string which
is given to us.
Now let's say that this scenario where the pointer over here is pointing at this character, indicates
the scenario where we are considering the substring that starts at h and goes up to the character t,
okay, which is in this case hot spot or the complete string.
All right.
So we have established that we have a pointer.
And the scenario where the pointer is over here represents the case where we are considering the substring
that starts over here and goes right till this character okay.
Now if this scenario has to give us the output as true, we know that that would mean that the entire
string over here, or the string that starts at H and goes up to T, can be made from words in the word
dictionary.
Okay.
So if that is the case, it would mean that there is a word in the given word dictionary that ends at
the character at this particular index, which is t.
Okay.
So there should be a word in word dictionary that ends with the character t.
Only then it's possible that this over here this scenario would return true.
Okay, so let's make some space over here.
And to check whether this is the case, we would have a for loop where we consider every word in the
given word dictionary one at a time.
And every word has a particular length.
Okay.
And we will check whether the substring that can be formed starting at index I minus length of the word
plus one.
Till index I.
Okay.
So that's what we have over here.
If this is index I then if we subtract the length of the word from I.
For example, let's say we got the word spot which has length four.
So over here I is at index 0123456.
So when we do six minus four that's equal to two.
And that's over here right.
So 012.
And if you do I minus length of the word plus one will come to this particular index which is three.
Okay.
So what we discussed over here is we are going to take every word one word at a time.
And we're going to check whether the substring that can be formed from index I minus length of the word
plus one to I is in the word dictionary or not.
And again let's quickly run over this once more.
So initially let's say we are considering the word hot okay.
And the length of this word is three and I is over here which is at index six.
Okay.
So 0123456.
And over here when we are considering six minus three plus one that's equal to four.
So we are considering the substring that goes from index four up to six okay.
And that's POT456.
Right.
So we're going to check whether p o t is in the word dictionary.
And we see that it's not.
Therefore we proceed to the next word which is spot okay.
And again I is at index six and six minus four.
The length of this word is four.
So six minus four plus one gives us three.
That's this over here this index.
And then we are considering the substring that goes from index three up to six which is spot.
And we see that spot is there in the word dictionary.
And therefore yes probably it could be that we are able to make this whole substring using words from
the word dictionary.
But more of that later.
So this is the first step.
We're trying to go over every word.
And we're going to see whether we can form a word in word dictionary using few of the last characters
in the given string.
Now let's make some space over here.
Now let's say for doing this, we have a particular function.
And we are passing this particular index to the function over here.
And you can name it as you wish.
Now once we see that this is true, let's say we got spot and we saw that that's true.
What remains to be checked is whether the remaining part in the string can also be formed using words
in the word dictionary.
And for that we would need to identify this particular index.
Again.
Notice we had I over here which was the last index of spot.
And the remaining part is hot.
So again we would need to identify this particular index which would be I minus length of the word.
Again notice I was six over here and the length of this word is four and six minus four gives us two
which is the index of this particular character okay.
So this character would be at index I minus length of the word.
And then we would just pass this particular index.
To the same function that we called over here.
Okay.
So that would be step number two, which is that we will call the same function with the input parameter
as I minus length of the word.
And for us to be able to form the whole string which is given to us using words in word dictionary such
that we make this part one particular word, which is what we have done so far.
For that to be true, this part also should return true, or this particular call to the same function
should also return true.
Okay, so this is the approach that we are going to take for the recursive way of solving this question.
And remember any recursive solution has a base case as well as a recursive case.
So we have discussed over here the recursive case which is we start at this index and we try to identify
whether there is a word in word dictionary such that this character becomes the last character in one
of the words in our dictionary.
And for example, over here we saw that yes, that's possible if we take the word spot, which is there
in the word dictionary, and then we identify this index which is I minus length of that particular
word, and we recursively call the same function again.
So this is the recursive case.
Now what about the base case.
The base case would be if the index is less than zero then we would just return true okay.
And again remember the base case can be thought of as the first invalid case.
And an index which is less than zero is an invalid case okay.
An index up to zero is valid.
And when you get an index for the first time which is less than zero, that's the first invalid case
that you have encountered.
And we can use that as the base case.
Now if we encounter the base case, we can just return true.
And you can think of this in two ways.
The first way of thinking about this, to understand why we can return true, is that if you are just
given an empty string, you can just do nothing and you have formed that string right now.
A better way, probably, to think of this would be let's say you're given the string hot.
Okay.
And let's say you have a word dictionary which has hot and a few other words.
Now again you start at this index and you identify that there is a word in the word dictionary hot.
And therefore you go ahead and try to find I minus length of the word, which is what we did over here.
Okay, I minus length of the word.
So when you do that you will come over here okay.
That's what happened over here.
Right.
So we started at T and when we did I minus length of the word we came to this position okay.
And in this case it was a valid index.
But over here when you do that you will get an index which is less than zero.
And in that case, logically we can return true because we were able to form the entire given string
using words in word dictionary, which is hot in this case.
Okay, so that's why if I is less than zero, that would be the base case.
And if we hit the base case we will just return true.
So this is the recursive approach for solving this question.
Now let's go ahead and memoize this.
Now memoization.
After you are done with writing, the recursive solution is pretty straightforward.
As you have seen in the previous questions that we have discussed.
So you just need to store what you compute.
And then before you go ahead and compute something, you have to check whether you have already computed
this previously or not.
So that's all about memoization right?
So let's say again hotspot is the string which is given to us.
Now for memorizing the solution we will need a DP array which will have n cells okay.
So this is going to be the DP array that we have.
And then at every index we will either store the value true or false.
For example this cell over here represents whether this substring which starts at h and goes up to O,
can be formed using words from the word dictionary.
In a similar manner.
This cell over here represents whether the substring that starts at h and goes up to p, which is hot
soup, can be formed using words in the word dictionary or not.
Similarly, this cell over here represents whether hot spot the entire string can be formed using words
in word dictionary or not.
So this is how we are going to solve this question.
And notice this is just the recursive approach itself.
And the only difference is that we are storing things that we compute.
For example, again we start over here and we're going to check all the words in word dictionary to
identify a word that ends in t.
And we'll see that we have spot okay.
We'll identify that this word indeed is there in word dictionary.
And then we'll get to this character which is I minus length of the word.
And we will check whether there is a word in word dictionary that ends with t.
And we'll identify hot and we'll see that yes, indeed this part over here can be formed in.
Read using words in our dictionary.
Okay.
And then when we go to I minus length of the word for this case we'll hit the base case because at this
point I would be less than zero.
And in this manner we will first fill through over here okay.
And then using this true we will identify that this also can be filled as true.
And that's how we solve this question.
So this is the memorization approach for solving this question.
Now you may have a question in your mind are there overlapping subproblems over here or not.
Because as we have discussed previously, memoization is a dynamic programming technique which is to
be used when there are overlapping subproblems.
But probably you may feel that when you take a look at this question, there are no overlapping subproblems
right now.
To clarify this doubt, let's take another example to make overlapping subproblems very, very clear
okay.
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
b.
Okay.
And let's say the word dictionary has these three words b b b and b b b.
Okay.
Now let's go ahead and write the indices over here.
So we have zero, 123 etc. up to ten.
And initially we are going to start over here okay.
So we will be calling the function that we will write.
And the input parameter would be ten okay.
And at this point we will see that there is a word b b b okay.
Let's say we first take a look at this word.
Again.
It depends on how we go through the words in word dictionary.
Now you can imagine that let's say this is the first word in word dictionary.
And because we get a match we identify I minus length of the word which is three.
So ten minus three gives us seven okay.
So we are over here and we make this call f of seven.
And at this point let's say we see this word in the dictionary and we see a match.
And therefore we come over here.
Okay.
And that's F5 and EF5, which is over here will return false because there is no word in word dictionary
ending with an A, so we'll not get any match over here.
And for that reason this will return false.
And therefore F of seven also will return false.
And then f of ten will try another combination.
Okay.
So let's say it at this point sees that there is B.
So F of ten will call F of eight.
Okay.
And f of eight.
Let's say it's seeing this b.
So it identifies a match over here.
And it calls F of seven which is what we have over here.
And let's say at this point it identifies B as a match.
And therefore f of seven calls f of five.
Okay.
And we reach over here.
And at this point because you have an A over here and there is no word in our dictionary ending with
an A, F of five will return false.
And therefore f of seven will return false and f of eight will return false.
And it goes on in this manner.
Okay.
But again our aim is to just identify that there are overlapping subproblems in this question.
And again now it's very clear.
Right.
You have F of five over here and you have F of five over here.
You have f of seven over here.
And you have f of seven over here.
And it goes on like that.
Right.
So in this example it's very clear that there are overlapping subproblems.
And that's why using memoization helps us to get a much better time complexity.