Welcome back.
In the previous videos we have discussed the recursive as well as the memoization approach for solving
this question, and we are discussing the approach number two, when we consider the two broad headings
that we had previously discussed at the start of this question.
Okay.
So we had discussed the tabulation approach for approach number one.
And then we discussed the recursive as well as memoization approach for approach number two.
Now in this video let's get started with the tabulation approach for approach number two.
And to discuss this let's take this example where the string given is hot spot.
And the words in the word dictionary are hot and spot.
Okay.
So we will be using a one dimensional DP array which will have n cells where n is the length of the
string which is given to us.
And initially we will just fill every cell over here with false okay.
And then we will have a pointer.
Let's just call it I and I will take the values from zero up to n minus one.
And for each value of I like let's say I is over here which is at one.
So when I is one, we are considering the substring that starts from h and goes up to O.
Okay.
And let's say when I is equal to two, we will be considering the substring that starts from h and goes
up to two.
So this is the way that we will be proceeding.
And for each substring we will check if there is a word ending at the character at that particular index.
Okay.
And for example over here when we see hot we will check whether there is a word in our dictionary which
ends at this particular t.
And again the word has to be an exact match.
So when we are over here we will identify that there is a word hot in word dictionary.
And when we see that it's a yes, we will check whether it's the first word which is the case over here.
Okay.
Which means there are no characters before it.
And that's one possibility okay.
And if there were something before it, like if you have let's say you have a character K over here.
So if you have something before it we will check whether the previous part also can be formed using
words in word dictionary.
Like if you had a k over here, then it would mean that the previous part can also be formed using words
in the dictionary.
And if you have a yes over here and either of these is true, then we would fill true in that particular
cell in the DP array.
And if neither of these are true then it would stay false.
So this is the way that we will be solving this question.
Now the best way to see how this pans out is just to dry run the algorithm.
So let's do that.
So initially I is over here which is at the value zero.
And we have only one character.
And we see that there is no word in the word dictionary of length one.
And therefore we just proceed to the next possible value for I.
So I takes the value one.
And we are considering the substring H0.
And the length of this substring is equal to two.
And again there is no word in the dictionary of length two.
So we proceed.
So I takes the value two okay.
And at this point we are considering the substring h o t hot.
And we see that there is a word in the dictionary hot.
So you have a word over here.
And we see that it's the first word okay.
Or there is nothing before it.
And for these reasons because we have a yes over here.
And this is true therefore over here we are going to change this false to true.
Now we proceed further.
So I takes the value three and I is over here and we are considering the substring h o t s.
And we see that there is no word in our dictionary which matches with h o s, right.
So therefore this stays false and we proceed further and we are considering h o t s p.
Again, there is no word in word dictionary that forms the ending part of this particular substring.
Again, it does not need to form the complete substring.
We just trying to see if there is a word in word dictionary that can form the ending part of this particular
substring, like for example, if there was a word over here like s p, then we would have got a yes
over here and we would check whether either of these is true.
But again we are not getting that.
And for that reason we just proceed further.
We come over here now we are considering the substring that starts at h and goes up to O, where again
trying to identify whether there is any word in word dictionary that can form at the ending part of
this particular substring.
So we have over here and when we see hot, hot does not match with O.
And then when we come to spot we are trying to compare spot with the ending part of this substring.
And again it does not match.
And for that reason we proceed further.
We come over here and when we come over here, we are considering the substring that starts at h and
goes up to t, and we see that there is a word spot such that it matches with the ending part of the
substring that we are considering.
So we have spot over here.
So that means we get a yes over here.
And we see that this is not the first word.
So this is not true.
And we are checking whether the previous part can also be formed from words in word dictionary.
And for that we just need to check the value that we have in this particular cell over here okay.
So when we do that we see that we have true over here, which means that the previous part can be formed
using words in word dictionary.
And for that reason over here we are going to fill true okay.
So this cell over here takes the value.
True.
And that's because we have a yes over here.
And this is true okay.
So this is how we were able to fill the DP table.
And the answer will be over here which is the last cell.
Because notice this cell represents the substring that starts at h and goes up to t which is the original
problem which was given to us.
So that's why whatever we fill over here will give us the answer.
And we finally just need to return whatever we were able to fill over here.
And in this case we are returning true.
Which means that hot spot can be formed using words in this word dictionary over here.
So this is the tabulation approach that we can use to solve this question.
And notice over here we are using only a one dimensional array as opposed to a two dimensional array,
which we had used in the previous tabulation approach for solving this question.