Welcome back.
In the previous video we have discussed the recursive as well as the memoization approach for solving
this question, and we are discussing the second approach for solving this question.
Now let's go ahead and write the pseudocode so that it becomes very clear how we are going to programmatically
implement the approach that we discussed.
So we will need a recursive function.
Let's just call it check.
And to this function we will be passing an index.
And again that's what we discussed right.
So initially we will be passing this particular index.
That's n minus one.
If n is the length of the string which is given to us okay.
So this is the starting point for this.
And we have also discussed the base case which is that if the index is less than zero then we will just
return true.
And again we have discussed already why we can return true in this case.
So if you are not remembering that please go ahead and take a look at that.
In the previous video where we have discussed the logic for this in detail.
So this is the base case.
Now after the base case before we go ahead and implement the recursive case.
Over here, we will first check whether we have already computed the substring that goes from zero up
to the particular index at hand.
So whether we have already computed whether this particular substring can be formed using words in word
dictionary or not.
Okay.
So for checking whether this was already computed previously or not, we will just check whether depee
at index is not equal to minus one.
Again, initially we will be filling all these cells with the value minus one.
And if we see a case or if we see that DPI index is not minus one, it would mean that we already computed
it and stored it over here.
And that's the reason why DPI index is not equal to minus one.
Now this is the typical thing that we always do for the memoization approach.
So this should be very straightforward.
And if this is not the case then we will go ahead and implement the other things that we discussed.
For the recursive solution we will find whether the substring that starts at index zero and goes up
to the particular index at hand can be formed using words in dictionary or not.
And once we have found that, we will either store true or false at dpi at index and then we will return
true or false.
So that's how we're going to do this.
So over here let's have a for loop.
So for word in word dictionary.
So we're considering every word in the word dictionary.
And we will check whether the substring that starts at index I minus length of the word plus one and
goes up to index I.
Okay.
So that's the first criteria over here whether this particular substring is in the word dictionary okay.
And if it is in the word dictionary we will check whether the remaining part in the substring can be
formed using words in word dictionary.
And for that we are recursively calling the check function again over here and over here.
The index that we will be passing to.
This would be the index which is previous to this particular index, which is the starting index of
this substring that we are considering.
So over here we will be passing the index I minus length of the word.
Notice we have I minus length of the word plus one over here.
And if you subtract one from this you will get I minus length of the word.
And again we have discussed this in detail in the approach video which is the previous video.
And so if this particular substring is a word in word dictionary, and if the previous part of the substring
that we are considering which is zero to index can also be formed using words in word dictionary, then
we will just store and return true okay.
So store means we will say dp at index is true.
And then we will just return dp at index.
And if we were not able to return true over here, after we have gone through every word in word dictionary,
we will come to this line of code where we will just return false.
Okay, because we were not able to return true, which means that we are not able to form the substring
that we are considering, which goes from index zero up to the index at hand, which is this index over
here.
So it means that we were not able to form that particular substring only using words from word dictionary.
So this is the pseudocode for the memoization approach for solving this question.