Hello all and welcome back.
So in this video we are going to continue our discussion on recursion and string and solve one more
question.
So the question which we are going to solve in this video is palindrome.
So our aim is that given a string we have to tell if a particular if that particular string is a palindrome
or not.
So let's get started and solve this now for people who are unaware of what palindrome is, let me give
you an example.
This name, Nitin is actually an example of a palindrome.
The reason for this, no matter if you start from left or you start from right, if you will read it
out, it is going to be the same from both the sides, right?
Another example for that can be.
Malayalam.
So again with this from both the direction it is exactly the same.
Right.
So these are the examples of palindrome and example which is not a palindrome of course ABC okay.
It is of course not a palindrome.
So let us now try to solve this question.
Everyone.
We must have done this similar question in using iteration and in Python.
Because of the powerful slicing concept, it is very easy, but you have to still make sure that we
solve this using simple, simple recursion code and not use the inbuilt functionality of Python.
Okay, so let's get started everyone.
First, let us try to understand and think of problem.
What I can think of if I am given a problem, given this particular problem, what I can do from my
end.
What I can do from my end is to check the starting and the last character, right?
If they are equal.
If they are equal, then maybe I can ask recursion to check for remaining character somehow.
Okay.
But first I should check okay if this is equal or not.
For example, in this particular ABC, a and C are not equal altogether, right?
So they are not equal.
Now we have already seen that we can actually have this start and end pointer here.
Right.
So something similarly I want to use here.
And this is the reason I have selected this particular question.
So that you get accustomed to using start and end pointer in string as well.
Okay, let me write the recursive relation as well for all of you.
Because the relation is something which we can also write here.
Now I am assuming that you are actually writing all the recursive relation for all the questions which
I am doing.
So let's say if I am given a particular string s, then what I have to do to write the recursive recurrence
relation s of zero equals equals s of length of s minus one, the last and the first character, and
so and or multiply palindrome.
And I have to somehow just make sure that I am able to get this particular part of my string right.
So why I indexing that can be easily done.
That is something like this.
So it can be length minus one.
This is how we do it by indexing everyone.
Right.
So I can show you an example as well.
Just let me show you an example here.
So let's say if my s is equals to nithin length of s is going to be five.
Length of s is going to be five.
Let me take it in N.
What I'm saying is if I print s of one to n minus one, then I will remove the first and the last character.
Right?
Oh, yeah.
So see I'm getting it I the first character is removed and the last character is removed.
Now this is very properly explained in the slicing concept that how we can do the same.
So I am just using this particular concept.
We can do one more thing as well.
Now this is this I am discussing in depth, because this is something which we are going to use in lots
of your string question.
So we can have a end and start which can be length of s minus one okay or n n minus one.
And I can create my function where I am now.
After comparing this I am using the same string, but I am going to send s plus one and e minus one.
So start plus one and n minus one.
So what exactly is happening in this particular case?
Everyone?
I am saying that if Nitin is my string.
I am going to take my start equal to this.
Or let me use another pen.
Yeah, I'm going to take my start equal to this and end equal to this.
Now in the next call I am just going to increase these pointers.
So my start is going to become this and end is going to become this right.
Something which you have already used.
But I want to still make sure that you can imagine that how it is so powerful in string as well.
Okay, so let me remove everything now and let us try to solve this question.
I am just going to make a function palindrome.
Okay.
It's going to get a string S1.
And it should just return if it is a palindrome or not.
So I am just it's going to return true or false.
Okay.
And let us pass Nithin only as an example.
Now pay attention everyone that what exactly is going to happen here?
Now I can create a helper function here.
So just so you remember this as well, I am creating a helper function so I can just do this length
of S1 minus one.
Now this palindrome helper is where I'm going to get my answer.
So def palindrome helper s1 start end end right.
Now if the very first is the base case, if start is greater than or equal to end okay.
That means that my string, my string is actually having the length equal to 1 or 0.
So I can return true.
Now this actually is our base case.
So maybe let me discuss this as well with you all.
What exactly is going to be our base case and everything okay.
First let us see what the base case is going to be.
Now the base case is actually going to be the same.
Only if my length of string is equals to 0 or 1, because a single character is a palindrome.
And similarly a string with no character is also a palindrome.
So I can return true.
Second, we discussed Can be the recursive call.
Now for the recursive call, we have seen both the ways we can either slice our string, or we can just
use the start and end character.
Slicing creates a new string in the memory start and end.
We are referring to the same string altogether.
Okay, so here we are just going to do S1, which is the string start plus one and end minus one.
Just one more thing.
If we are talking in terms of start and end, then if start is greater than or equal to n, then we
say this is the base case okay.
Because let us say if it is n I t I n if both s and e are here, that means start is equal to end okay.
But if start is ahead, start is ahead of my end.
Then we have actually messed up something because that is kind of a negative length string or a zero
length string okay.
So we are saying that yes we have transferred the whole string.
This thing would have been a lot clear because we have done binary search and everything as well.
Right.
But yeah, I want to just make sure that you understand and able to visualize how these concepts are
interdependent on each other.
So you clear this concept one properly.
It is going to use everywhere.
Okay.
So this is how I'm going to do the recursive call.
And third can be r work.
Which is just checking if s one of start equals to s one of n right now of course these are something
which can be interchanged.
So we we in this particular code are going to do our work first okay.
So pay attention everyone.
If s one of start is equals equals to s one of end.
Or let me make not equal to right.
Then we can return false directly because we don't need to check afterwards.
Right.
If the first one is not correct, if this would have been Nithin okay then of course this n and this
m is not equal to each other.
And hence I can comfortably say that the string as a whole will not be palindrome.
I do not need to even wait for recursion, Equation, right?
If that's the case, if sorry, if that's not the case, if they are equal, then the answer will depend
on recursion.
Answer.
And I can just return whatever recursion says to me okay.
So yeah I hope with that it is clear and the answer is true.
Let us check for Malayalam.
The answer is true.
Let us check for a, b, c, d or a b c d a.
The answer is false, right?
So I hope this code is clear.
Now I am making sure that I'm explaining you pretty easily and by going step by step.
The reason is that once you are understanding of this, basic questions are clear.
You will be able to code the difficult or medium questions a lot more easily.
Okay, so let me just run this once for Nithin.
Let me just show you the function calls for Nithin as well.
Meanwhile.
Okay, so what exactly is going to happen?
We are going to call the Nithin here, okay?
And this is going to be zero.
This is going to be five for okay.
Because Nithin This is 01234.
Right in the very first, in the very first case.
This is my start and this is my end.
And I see that they are equal and I see that they are equal.
Okay.
From a code perspective your work is done here.
You can just now let recursion handle the same okay.
You don't need to draw this.
And that is something which I have been repeating so many times.
But to understand the same for understanding perspective let us draw this.
So we are going to get this particular thing in the starting function.
Then next going forward.
I am going to get my start and end as one and one second.
Let me use different color one and three.
Now one and three are also equal.
So I am going to make the call again.
This time both my start and end are equal to two.
And if you will see this is actually my base case right?
If start is equal to end then this is the base case everyone.
And because this is the base case I am going to return true from here.
Now we have already checked for our work.
We have already done so whatever is getting returned, just as happened in recursion, I am going to
return my answer as true everywhere.
Okay.
So yeah, I hope that helps you to understand it properly.
Everyone.
This is how the flow is going now.
Okay, I mistakenly typed it R but we can see the same now.
It is false.
Okay, you could have done by making the palindrome helper call first as well.
We have shown you lot of times that okay this is interchangeable.
But I hope in this problem you can understand that.
Why doing R work first is helpful and normally faster.
Okay.
So yeah I hope with that this question is clear.
Just a request.
Please make sure that you are running this question on Python tutorials or try to draw this particular
tree once.
Okay.
Moving forward we are going to do some medium to hard level questions which are going to actually now
test your skills of everything which we have done in recursion.
So yeah, please make sure that you have done all the assignments and you do these questions the way
I am asking you and everything.
Recursion is going to be a breeze for you.
Okay, cool everyone.
So let's meet in the next class.
Thank you.