Let's now go ahead and implement the tabulation approach that we have discussed in the previous video.
Okay.
So we are given the string s over here.
Now let's say n is equal to s dot length.
And we will need a DP array.
So let's call it dp itself.
And this array will have the same size which is n.
And we will initially fill every cell in this array with the value false okay.
And again we are going to make this DP array in a way that at every index this would have either the
value true or false.
And it will have the value true.
If the substring that goes from zero up to that particular index can be formed using words from word
dictionary, and therefore ultimately we would just need to return depee at n minus one, which represents
whether the whole string, that is, the string that goes from zero up to index n minus one can be formed
using words from word dictionary.
All right.
Now we are going to have a variable to iterate over the various indices of this particular depee array.
So let I is equal to zero I less than n I plus plus okay.
And for every value of I we are going to go through every word in the word dictionary.
So I can say for let word of word dictionary okay.
And our aim is to check whether we can find a word that we can fit towards the end of the substring
that goes from zero up to index, I.
Okay, now again, before we do that, check over here, if we find that I is less than word dot length
minus one, then there is no point to check this and we can just continue to the next word.
Okay.
So we are skipping that and continuing to the next word because I itself is less than word dot length
minus one.
Now if this is not the case, then we will check whether the substring that can be formed in the substring
that we are considering that goes from zero up to I.
Okay, so we have to find the ending part of that particular substring, which has the same length as
the length of this word over here.
Okay.
So for that we need to calculate the start index which would be I, which is actually the end index
minus word dot length plus one okay.
So that would be the start index.
And we have to take the characters till index I.
So that's why we have I plus one.
Now we are going to check whether this substring over here is equal to the word that we are considering.
Now if this is true then we are going to check either whether I is equal to word dot length minus one
okay.
Which would mean that this is actually the first word, or there are no characters to the left of this
particular start index.
So either this has to be true or if there are characters to the left of this start index, we want to
check whether the substring that goes from zero up to the character before this start index can be formed
using words from the word dictionary, and for that we just need to take a look at depee at I minus
word dot length.
Okay, so either of these has to be true.
So if this is true and if either of these conditions is met then we can say depee at index I is equal
to true.
And we can just break out of this for loop okay.
So in this manner we will fill the DP array.
And finally once we are done with this we will come over here and we will just return DP at n minus
one.
All right.
Now let's go ahead and run this code and see if it's passing all the test cases.
But I see there's something wrong over here okay I've made a typo.
So let's correct that.
And let's run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.
So this is the tabulation approach using a one dimensional array for solving the word break question.