Okay, so welcome back to the stl challenge 1 solution.
I'm in section 20, and I'm in the challenge 1 solution project.
And this is the project where we had to write the is palindrome function.
So hopefully, you were able to solve this problem.
It's actually quite simple when you think about it, so let's talk about it.
The idea is -- we're going to use a deque.
So the idea is let's say that we have a string like aabaa, that's
obviously a palindrome, right.
It reads the same from the front or from the back.
So what we -- then that's coming in here is my string.
So what I want to do is I want to create this deque
of characters right here.
And I just want to push these characters into the deque.
So I'm going to grab that, and I'm going to push back.
So I'm going to basically create a deque that looks like this.
I'm going to push the characters onto the deque.
And then what I'm going to do is I'm going to check the front
of the deque and I'm going to check the back of the deque, grab
whatever's there compare them.
If they are the same, then I process them, remove them and
move on to the next ones, right.
Compare them.
If they're the same, I'm going to remove them.
At that point, if I end up with an empty deque or a deque with just one item
in it, then i know it's a palindrome, it's as simple as that for something
like, let's say, 4 so I'm going to grab that string, put it into the deque.
I'm going to grab the first character here in the front.
I'm going to grab the last character here in the back.
They are not equal.
So there's no way this can be a palindrome. So I'm out right there.
Okay, so let's walk through the actual code.
So now you know the algorithm is pretty straightforward.
So let's look at the code right here.
Here's the is palindrome function.
And I've got a deque, and I'm initializing it to an empty
deque, I'm just calling it d.
Then for each character in this string s, if the character is an
alpha, right, so in other words it's not white space, it's not a
digit, it's not special characters.
So if it's if it is alpha, then what I'm going to do is I'm going
to convert it to uppercase and push it onto the deque in the back.
That's it.
So once this loop is done, whatever was in this string is now in the
deque minus the special characters and the white space and everything else.
That's it.
Now I've got two variables here c1 and c2.
Those are the variables that I'm using to store what I'm reading from the
front and from the back of the deque.
And now I'm going to do something right here.
This is my loop.
It's really simple.
While the size of the deque is greater than 1, then I want to keep processing.
Once I hit 0 or 1, I'm done, right.
It's got to be a palindrome.
So I'm asking the deque, okay, give me your front element,
give me your back element, and I'm storing those in c1 and c2.
I'm getting rid of those two elements from the deque.
I don't need them there.
And then I'm comparing them.
So if c1 is not equal to c2, then the characters can't be the same.
There's no way this can be a palindrome.
So I'm returning false immediately.
If I get through the loop, I'm returning true.
It's got to be a palindrome.
So that's it that's the solution.
And as i said, this is a very common problem given in a coding interview.
And what the interviewer wants is for the applicant to try to
solve it a different way and then say oh by the way, can you solve
it using a deque, and that's it.
So you can see it's a real simple solution.
No iterators, nothing fancy, no algorithms.
You're just using the front and the back of the deque,
just like we're supposed to.
All right, so I hope you enjoyed this challenge.