Let's now get into the code and write the recursive approach that we have discussed in the previous
video.
So we again given S which is the string, and we given our dictionary.
Okay.
Now let's say n is the length of the given string.
And we will need a helper function.
Let's just call it check ending hat.
Okay.
And to this function we'll have to pass an index.
Now again what is this function going to return.
This function will either return true or false.
And it's basically checking up to this particular index over here from zero.
Whether that particular substring can be formed with words from word dictionary.
Okay.
And when we call this function for the first time, we will have to pass the last valid index which
is n minus one because n is the length of the string.
Okay.
So this actually would check whether the complete string that is from index zero up to index n minus
one can be formed using words from word dictionary.
And because this will either return true or false, we can just return what we get back from this.
So this is the skeleton of the approach that we are going to implement over here.
Now let's go ahead and write the details.
So over here we'll be writing the base case as well as the recursive case okay.
And the base case would be the case where the index is less than zero which is the first invalid index.
So if index less than zero then we can just return true.
Now why do we return true.
We have discussed this in the previous video, but let me quickly review this.
Now let's say word dictionary has just one word.
Let's say it's good and let's say s is also good okay.
And let's say we are passing this index over here which is three.
Now once we see a match between what we have in our dictionary and what the string which is given to
us, and again, we're just considering the substring from zero up to this particular index.
And again in this example we see these two match.
So from here we will be moving back four units which is the length of this particular word okay.
And we would reach over here.
And this is actually less than zero okay.
And that's why we return.
True.
And this is the only way that this would happen.
Because in the question again it's mentioned we will not be given an empty string.
And for a scenario to happen where index is less than zero, this would be the case okay.
And again that's why we can return true in this case.
Now let's proceed to the recursive case.
And for this we would have to iterate through every word in the word dictionary.
So I can say for let word of word dictionary okay.
And we have index over here which is the ending index.
And because we are considering this particular word we'll have to calculate the start index.
And start index is going to equal the end index minus the word length plus one okay.
So that gives us the start index.
And now we will just check whether s dot substring from start to index okay.
So we'll just check whether this particular substring is equal to the word that we are considering.
And if this is true then we will also check whether the previous part of this particular substring can
be formed using words from word dictionary.
And for that we will be just calling the check ending at function recursively.
And to this we will pass the index as start minus one, which again is the ending index.
Okay.
Now if these two conditions are true then we will just return true, which means that we can form the
substring that goes from zero up to.
This particular index can be formed using words from our dictionary.
And if we are not able to return true over here, and once we come out of the for loop, we will just
return false.
Okay, so this is the recursive solution to the word break problem.
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.
Now in the next video, let's go ahead and memorize this to achieve a much better time complexity.