Let's now get into the code and implement the tabulation approach using a 2d dp array, which we have
discussed in the previous video.
So we are given this string s over here.
And we are also given this word dictionary which is an array okay.
Now let's say n is the length of the given string.
And let's also create a DP array which will be a 2D dp array which will have n rows and n columns.
So let's go ahead and do that.
And we will need n columns okay.
And what we will do is we will fill every cell in this DP array with the value false okay.
Now let's go ahead and iterate through the cells in the DP array in a length wise manner.
So we can say for let L is equal to one l less than equal to n l plus plus.
And then we can say for let I is equal to zero I less than or equal to n minus n I plus plus and j is
going to equal I plus l minus one.
Now remember every cell in the DP table will either have the value true or false, and we will set a
value in a particular cell to be true.
If the substring represented by that particular cell can be formed using words from word dict.
So that's the criteria okay.
So we have a combination of I and j at this point.
And we will first check whether the complete substring which goes from I to j is a word in verdict okay.
So for that I can say if word dict dot includes s dot slice okay that's slice.
And we have I comma j plus one.
Okay.
So we are checking whether the complete word is a word in the dictionary.
And if that is true then it's pretty straightforward.
We can just set dp at ij to be equal to true.
But if that is not the case, then we are going to check whether we can make a partition for the substring
such that the two partitions can be formed using words in word dictionary, and if that is possible,
it would mean that we can form the complete substring that goes from I to j using words in the word
dictionary.
Okay.
And again for this we will use another variable and for let k is equal to I k less than j k plus plus.
So notice k takes values from I up to j minus one.
And again this is the same thing that we did in the palindrome partitioning question okay.
And over here we will say dp at I j is equal to dp at I j or the partitioning okay, which is dp at
I k and dp at k plus one j okay.
And again notice it's important that we have and over here because we need both these parts to be true.
Only then it would mean that DP at I j can be set to true.
Because if both these parts can be formed using words in the dictionary, then the substring that goes
from I to j can also be formed using words in word dictionary.
Okay, so that's it.
Now once we are out of this for loop, we would just need to return dp at zero n minus one okay.
And again notice the cell zero n minus one in the dp table represents the substring that goes from index
zero up to index n minus one, which in fact is the input string which is given to us.
Right.
So that's why this cell will hold the answer.
Now let's go ahead and 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.