Hey there and welcome back!
In this video, let's take a look at the recursion tree of the approach that we have so far discussed
for solving the palindrome substrings question.
So let's say this is the string that is given to us.
Notice that the last valid index is equal to five and the first valid index is equal to zero.
Now we have already written the ace palindrome function.
So first we will be passing zero and five to this function.
And inside the body of this function we would make a call to the same function recursively passing zero
and four and one and five.
So again notice that over here we are only moving one pointer at a time.
And then we will also be checking whether p over here is equal to s.
And we see that these two characters are not equal.
And therefore the string that starts at index zero and goes up to index five is not a palindrome.
And this problem over here is represented at this cell in the DP table.
Because notice the start index over here is zero.
And the end index is equal to five.
So the string represented by this cell over here is not a palindrome.
And we can fill false over here.
Let's continue.
Now the call over here to the same recursive function which passes the indices zero and four will make
again recursive calls.
And the indices that would be passed to the same function at those instances will be zero comma three,
one comma four.
And then we would also check whether this string over here, which starts at index zero and goes up
to index four, is a palindrome or not.
Again, in these two cases we are only moving one pointer at a time.
And over here when we check the characters at index zero and four.
We see that these two are equal.
And again, the string that we are considering is not of length two.
So we would check the substring that starts at index one and goes up to three to identify whether the
whole substring over here which is being considered is a palindrome or not.
Now when we do this check that goes from 1 to 3, we see that this is not a palindrome.
So this would return false.
And therefore we know that the string that goes from zero up to four is not a palindrome.
And that's represented by this cell in the DP table.
And we fill false over here.
So you can see that the way that this proceeds is pretty straightforward.
And in this way we would be able to fill the DP table over here with either true or false true indicating
that the substring at hand is a palindrome, and false, indicating that the substring at hand is not
a palindrome.