Welcome back.
In the next few videos, we will be discussing the memoization and tabulation approach for solving the
palindromic substrings question.
So let's get started with the memoization approach.
So let's say the string that is given to us is p q p r p s.
Okay.
So let's say this is the string that is given to us.
Now how would the memoization table look like?
We would need a table that can represent all the possible substrings that can be formed.
So that is why we will have p q p r p s on the columns to indicate each of these characters, as well
as rows to indicate each of these characters.
So the DP table would look something like this over here.
So let's write the indices over here.
That's 012345.
So you can see that we have one column for each of these indices and one row for each of these indices.
So if this is the DP table that we will be using what does each cell represent.
For example what does this cell over here represent.
So this cell over here notice has one as the row and three as the column.
So this cell represents the substring that starts with the character at index one and goes up to the
character at index three which is q p and r.
So in this way the row value gives us the starting index.
And the column value gives us the ending index.
And in this manner we will be able to represent all the possible substrings using this DP table over
here.
And then once we find that a substring is a palindrome, we will store the value true in that particular
cell.
And on the other hand, if we find that a substring is not a palindrome, we will store false in the
cell that represents that substring.
So this is how we will go ahead with the memoization approach for solving this question.
Now let's also discuss how we can use recursion to come up with all the possible substrings.
So initially we would be checking the substring which starts at index zero and goes up to index five.
So this would be inside a function call to a recursive function.
And over here inside the body of the function we would have to check whether this substring over here
that goes from 0 to 5 is a palindrome or not.
If it is, we would store true at the cell that represents this substring in the DP table over here.
And we would also check the substring that goes from 1 to 5.
And from 0 to 4.
Now in these two instances, we are again recursively calling the same function, but we are only moving
one index.
So in this case we have moved 0 to 1, and in this case we have moved 5 to 4.
Again we have discussed in a previous video why this is necessary.
So using this approach we will be able to recursively ensure that we visit all the possible substrings
and either store true or false in the cells in the DP table that represent those respective subproblems.
Now, in the next video, let's go ahead and write the pseudocode for this approach.