Welcome back.
We have discussed the approach that we are going to take for solving the word break question.
And in this video, let's go ahead and write the pseudocode for the approach that we discussed.
So for solving this question using this approach we are going to use a 2D DP array.
That's what we have over here.
And its size is going to be n into n.
And initially we are just going to fill every cell with false okay.
And then we are going to iterate through the cells in the DP table in a length wise manner.
And again we have done this many times.
So let's go ahead and write the pseudocode for this.
So I can say for L taking the values from one up to n, and for I taking the values from zero up to
n minus l.
And for each of these combinations of l and I, j will take the value I plus l minus one.
And again, we have discussed this many times in previous videos.
Now once we have a combination of I and J, it represents a particular cell in this DP table over here.
Now to see whether DP at IJ, which represents a cell in the DP table over here, has to be filled with
the value true, which would imply that we can create that particular substring using words from the
word dictionary.
So to check that we will check two conditions.
The first condition is if the substring by itself is a word in word dictionary, or if the substring
that starts at index I and goes up to index j.
So if this substring by itself is a word in word dictionary, then we will say dp at I j is equal to
true.
Now the other possibility is we are going to check all the possible partitions to see whether there
is a partition such that dp at I k and dp at k plus one j.
Both are true, which would mean that this part over here can be created through words in the word dictionary,
and this substring over here can be created as well with words in the word dictionary.
Now if this is true, it would mean that dp at I, j can also be created using words in the word dictionary,
and for that reason we would fill dp at ij with true if we see there is such a partition.
And again this over here just checks whether both of these are true.
Okay, so this is how we are going to identify whether we can fill a particular cell with the value.
True.
And once we are done with this we would have filled all these values.
Right.
We have filled all these values.
And then we would fill all these values which are of length two and in such a manner, finally, we
would have filled this cell as well.
And then we will just return depee at zero n minus one, which is the value in this particular cell
over here.
Okay.
And again notice this cell over here represents the string that starts at H and goes up to T which is
in fact the original problem given to us.
And that's why returning DP at zero n minus one will give us the answer.