Hello, welcome to the section 20, challenge 4 video.
This, you've already seen before.
We did this challenge in challenge 1.
This is where we decided whether a string was a palindrome or not.
We use the deque in challenge 1.
What we're going to use here in challenge 4 is we're going to use a
stack and a queue to do the same thing.
It's actually exactly the same main driver.
The only difference is your function is going to be different obviously,
because it has to use a stack and a queue to solve the problem.
What I would ask you to do is go back to challenge one and play
the description video, where I go into what a palindrome is and so
forth rather than repeat it here.
But if you're here already, and you don't want to go over there,
I'll do a real quick review.
A palindrome is a string that reads the same backwards or forwards, so
we have a couple of examples here, madam, bob, toot, radar, so no matter
how you read it from the left or from the right, it's the same word.
And we can have entire phrases that are palindromes as well.
So, a Toyota's a Toyota, a Santa at NASA, a man, a plan, a cat, a ham,
a yak, a yam, a hat, a canal-panama.
It's amazing that this actually is a palindrome.
For palindrome phrases like this, what we're going to do is we're going to
remove all the spaces, and we're going to remove all the special characters.
And we're going to make those uppercase.
So, in the case of a santa at NASA, what we're going to do is we're
going to create that string from it.
You can see it says ASANTAATNASA right in there, but no spaces,
everything's uppercase.
And if there are any apostrophes or anything else,
we're going to get rid of it.
So, we're only going to process alpha characters.
And you can use the CC type header file for that.
That's it.
Good luck with this one.
Like I said, go back to challenge 1 description, and
I talk a lot more about that.
Actually, let me show you a sample run, so you don't have to go back there.
I'm going to show you a sample run of my solution here.
And I'll build and run the main driver.
I'll show you the code also in a second.
The main driver has a bunch of test cases that they run.
All you have to do is write one function, it's called, is palindrome
and it returns true or false.
I pass you a string, you return true or false.
So, in this case, a is a palindrome, aa is palindrome,
aba is a palindrome and so forth.
Obviously, ab and abc are not.
Radar, and bob, and ana, and avid diva, and there's a Toyota's
a Toyota, a santa at NASA.
C++ is also a palindrome because what we're doing is we're removing the
+ +. And just using the capital C, we're getting rid of the special characters.
So, there's some test cases and here you can see the man, the plan, the
cat, and so forth is a palindrome.
You can read it the same both ways.
So, that's the sample run.
And let me show you the main that I'm giving you, this
is the main I'm giving you.
It's the same exact main that I gave you for challenge 1 except what I
want you to do is I want you to use.
You can see right there.
Use a stack and a queue before we use the deque.
So, this will give you a little bit of experience with that.
You can see the main here and all I'm doing in the main is I've got a vector
of strings and those are my test cases.
And I'm just looping through that vector and I'm calling your
function is palindrome right here.
I'm passing in the string and you're returning true or
false, and I'm displaying that.
It's as simple as that.
Here's the function you have to implement, it's called is_palindrome.
It expects the string, and it returns true/false.
Right now, I'm just returning false for everything,
so if you run this right now, you're going to get...
Actually, I'll run it right now, so you can see what it looks like.
If I run this guy right now, it's going to say false all the way
down the line because there's no real logic in that function.
But it all runs, and compiles, and no worries at all.
So, that's it.
If you solve the problem with the deque, you kind
of know how to approach it.
I'm not going to give you any hints here.
If you want a hint or if you have questions, please post in the Q&A,
and I'll be glad to answer them there.
Alright, so good luck.
I'll see you in the next video.
And I'll show you my solution.