Welcome back.
In the previous video, we have discussed the tabulation approach using a one dimensional array for
solving the word break question.
Now let's go ahead and write the pseudocode for the approach that we came up with, which is what we
have over here okay.
So let's write the pseudocode for this.
So I takes the values zero up to n minus one.
Right.
So this is what we had previously discussed.
So let's write a for loop for this.
So I can say for I is equal to zero to n minus one.
And for each place of I we are considering the substring that starts at index zero and goes up to index
I, and we are going to check every word in the word dictionary to identify if there is a match such
that the ending part of the substring that we are considering can be formed from a word in the word
dictionary.
Okay, so we'll have to go through every word in the word dictionary.
And for that let's write a for loop.
So I can say for word in word dictionary.
And I will be checking if I is less than the length of the word minus one.
Because for example, let's say we are over here.
So the length of this substring is just two and the length of every word is greater than two, right.
So there is no point in comparing the substring at hand with the words in our dictionary, because the
length of the substring is lower than the length of the word we are considering in the word dictionary.
So for that, let's say if I is less than the length of the word minus one because I is zero indexed,
right?
So if I less than length of the word minus one, if that is the case, then we will just continue to
the next word.
And if that is not the case, then we will check whether the substring that we are forming is equal
to the word we are considering.
And if this is true, then we will check whether this particular word is the first word of the string
at hand, which is what we had when we got a match for hot.
Or we will check whether the previous part in the substring can also be formed using words in dictionary,
which is the case when we identified that the substring spot can be formed using a word from the word
dictionary.
And then we also saw that the previous part, which is hot, can also be formed using words in word
dictionary.
Okay, so if this is true and if either of these is true, that is, if the word is the first word,
or if the previous part after removing the word at hand.
So if the previous part can be formed using words in the dictionary.
So if this is true and if either of these are true, then we will set depee at index I to be true.
Okay.
And again to identify the substring at hand for the word that we are considering, we need the indices
starting at I minus length of the word plus one and it goes up to index I okay.
And I is what we have from the outer for loop.
Now for example when I is equal to two okay that's this case.
And let's say we are considering the word hot.
So its length is three.
So I is two.
So two minus three plus one gives us zero.
So this is zero and I is equal to two okay.
So that's how we get the substring that starts at index zero and goes up to two which is hot.
And we see that's equal to the word.
Let's say at that point the word in consideration is hot okay.
So we get this substring by considering the indices that start at I minus length of the word plus one
and goes up to I.
So that's it.
And once we are done filling the table over here, we just need to return the value in the last cell
which is dp at n minus one.
So we will just return dp at n minus one.
And this is the tabulation approach for solving this question using a one dimensional array.