So let's get started with approach number one.
Now to discuss this, let's take an example.
Let's say the string which is given to us is hot spot.
And the word dictionary has the words hot and spot.
Now to see whether we can form the given string using words from word dictionary.
And again that's the question at hand.
We will use a two dimensional DP array where we have rows as well as columns for every character in
the given string.
Okay, so notice over here I have hot spot on the columns as well as on the rows.
Now what we will do is we will iterate over each possible substring.
And we know how to do that by iterating length wise.
And then for every cell which represents a particular substring, we will check whether that particular
substring is in word dictionary.
So if that particular substring, the whole substring is a word in word dictionary, we will just fill
true in that particular cell.
And if this is not the case then we will check whether we can form that particular substring using words
from word dictionary okay.
And for that we will have another variable k which goes from I to j.
And again this is the partition method that we have discussed in the previous questions.
And if we see that depee at I, k and depee at k plus one j, both of these are true.
Then we will mark depee at I j as true.
Again, we have seen this many times in previous questions, so what we are doing is to identify whether
dp at I, j is true or false.
We are trying all possible partitions and for that we have another variable k and k takes the values
from I up to j minus one.
Okay.
So again this has to be j minus one if you consider these as values taken by k.
But again in some programming languages, if you write k in range I to j, it means that k takes values
from I up to j minus one.
So k takes values from I up to j minus one, and for each value of k we are making a partition.
For example, when k is I, this becomes depee at I I, which is just one character, and this becomes
dp at I plus one till j.
Okay.
And what we are checking over here is we are checking whether this is true and this is true.
So if both of these are true it means that dp at I k can be formed from the words in our dictionary,
or is a word in itself which is there in word dictionary.
And if dp at k plus one j is true, it means that this substring can be formed from words in word dictionary.
And if these two are true, it would mean that dp at I j can be formed from words in word dictionary.
Okay, so this is the logic that we are going to use.
And again we have done this previously where we used a variable k to make all the possible partitions.
And once we have done this and again let's quickly take an example.
For example, if we take a look at this cell over here, this cell would represent the substring that
starts at h and goes up to t which is hot.
And we see that hot is a word in word dictionary.
So we would be filling true over here because of this criteria.
Now what about this cell over here.
This cell represents the substring that starts at O and goes up to S okay.
So that's o t s.
Now over here when we check this criteria we see that o t s is not a word in the dictionary in itself.
And therefore this is not true.
Okay.
And then we check this part over here.
We make all the possible partitions to see whether we can get a partition such that dp at ik and DP
at k plus one j.
Both are true.
And in the case of OTS we will see that's not true and therefore over here we would be filling false
okay.
And again similarly if you consider this cell over here it starts at H and goes up to S which is hots.
And again hots is not a word in itself which is there in word visionary.
And there is no partition such that dp at ik and DP at k plus one j become true.
Okay, so you have hots and this not being true means there is no partition like you.
If you make a partition like this, you see hot is there in your dictionary, but S is not there in
word dictionary.
Okay, so there is no partition such that the partitioned parts could be made through words in word
dictionary.
And for that reason over here also we will be filling false.
So again I'm not going to dry run this because this is pretty similar to what we discussed in previous
questions in this section.
And once we have iterated through all the possible substrings, we will get our answer over here in
this cell.
Because notice this cell represents the substring.
That starts at H and goes up to T, which is in fact the string given to us.
So finally, once we have filled this cell, that will give us the answer and we will just return the
value that we fill in this cell, whether it's true or false.
So this is the first approach with which we are going to solve this question.
And notice that this is a tabulation approach or bottom up approach.