Welcome back.
In the previous videos we have discussed the memoization approach for solving the palindromic substrings
question over here.
Let's go ahead and write the pseudocode for the approach that we have discussed.
So because the memoization approach is a recursive approach, we would need to think of the base case
as well as the recursive case of the approach that we come up with.
So let's go ahead and make some space over here.
And let's call the function that we are going to write over here as is palindrome.
And to this function we would have to pass two variables.
And over here I've just called them I and j.
So I is the starting index and j is the ending index.
So by just having a combination of these two values we would be able to determine the substring that
we are evaluating.
So for example if I is zero and j is five we are evaluating the whole string.
And let's say if I is equal to two and j is equal to four, then we are evaluating prpp which is a substring.
And then we would be calling this function for the first time.
And over here we are passing zero.
And the last valid index which is length of the string given to us minus one.
And then over here recursively we will be visiting all the possible substrings.
And for each substring we will either populate true or false to the cell in the DP table over here which
represents that particular substring.
So this is the memoization approach for solving this question.
Now we have already discussed the recursive case which is to first check whether the substring that
starts at I plus one and goes up to j is a palindrome or not.
We would also have to check the substring that starts at I and goes up to j minus one.
So these are the two recursive calls to check these two scenarios.
And we have discussed previously why this is required.
So we are just moving one pointer among I and J at a time in these two calls.
And then we would also need to check whether the substring that starts at I and goes up to j is a palindrome
or not.
So for this we would have to compare the characters at indices I and j respectively.
So if these two are equal, then we would need to check whether either we are just dealing with a substring
that is of length two, or whether the substring that starts at I plus one and goes up to j minus one
is a palindrome or not.
So if this is true, and if either of these is true, then we know that the string or the substring
that starts at index I and goes up to j is a palindrome.
And we would fill true in the cell over here in the DP table that represents that particular substring.
So this is the recursive case for solving the palindrome substring question.
Now let's also think of the base case.
Now again we have discussed that this function over here will go through all the possible substrings
and fill either true or false in the respective places in the DP table, which represents the substring
at hand.
Now, when it comes to the base case, we just need to check whether I is equal to j, because in that
case we are dealing with a substring of length one and we can just return true.
And you will also see that in some solutions.
The base case also has this check that if j is less than I, or if the ending index is less than the
starting index, we can just return false.
Now you can go ahead and write this, but this is not required because notice that over here we have
a separate check to check whether the string at hand just has two characters.
So because we would get true over here for that we would not execute this recursive call where we just
have two characters.
So for example, if I is pointing to index zero and j is pointing to index one, then we would not call
the recursive function over here with I plus one j minus one, which would cause this type of a scenario
because over here first we are checking whether j is equal to I plus one.
So because of this we do not need this check.
But if you reverse this, if you write this first and then you write this over here, when you write
the condition to check whether this is a palindrome or not.
So if you write this first and then you write this, then you would need to add this as well to the
base case.
So we have discussed the base case and the recursive case.
And we are done writing the pseudo code for the memoization approach for solving the palindrome substrings
question.