Hello, welcome to the first challenge of the stl section of the course.
Now I didn't give you any vector challenges because you've done quite a
lot of vector challenges in the course.
So we're going to start with a deque, and I know a
deque is new to most of you.
So I'm in the section 20 workspace.
And here you can see the challenge_1 project.
And the challenge_1solution project.
The solution project obviously has my solution to this problem.
And the challenge_1 has the source code to get you started.
So let's talk about the challenge.
The challenge is all about using a deque.
So we know what a palindrome is.
Some of you may not know what a palindrome is.
A palindrome is a string that reads the same backwards or forwards.
So a simple example is madam, bob, toot, radar and
there's very many, many more.
So these are words that read the same forward or backwards.
Now we can have entire phrases can be palindromes.
For example, 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.
All these are great examples of entire phrases that are palindromes.
For the purposes of this assignment, we're only going
to consider alpha characters.
We're going to omit everything else.
So spaces, commas, exclamation points and so forth, apostrophes,
as we see here, will all be eliminated or omitted.
So when we read something like a Santa at NASA, what we're going to convert
that to is ASANTAATNASA, like that.
All uppercase, and get rid of all the special characters that --
and obviously, you know what to use.
You can use the cc type header file for that.
So how do you solve this problem.
Well, a common method to solve the problem is to process the string
you end up with something like that.
And then you reverse that string and you compare the two strings.
Obviously, if the two strings are the same, right, the one that's
normal and the one reversed, then it must be a palindrome.
But we're not going to do it that way, we're going to use a deque.
I'm providing a main driver for you that'll automatically run a bunch
of test cases, and your challenge is to write one function, the
function is called is palindrome.
It returns a true false value, and it expects a string.
So I'm going to send you a string, and you're going to return true or false.
The function, as I said, determines whether that string is a palindrome.
That function must take care of removing any spaces
and any special characters.
So here's a couple of examples.
Is palindrome "A Santa at NASA", that will return true.
Is palindrome "Hello" should return false because hello is not a palindrome.
All right, and what I'd like you to do is to use a deque to solve the problem.
After all, that's the section we're in, the stl section,
and the deque is a perfect container to help us solve this.
If you need a hint, please post something in the Q&A forum.
This is a very common question that's used in coding interviews.
And a lot of times, they'll start the coding interview
with solve this problem.
The majority of the applicants will try to come up with the
string, reverse it and compare.
And at that point the, interviewer will say could you use a data structure like
a deque to do it, and that gets a lot of people because all the books show you
how to do it with reversing the string.
But it's interesting to do it with a deque.
Let me run my solution so you can see the sample output.
And here's the sample output.
I've got a result, and I've got the string.
So in this case, you can see the lowercase letter a is true, aa is
true, aba is true, abba is true.
These are all palindromes, but obviously the ab is not a palindrome
nor is the abc radar and bob and ana are as are all these more complicated
phrases, even c++ is, right.
Once we get rid of the ++, we're left with a c, that's
definitely a palindrome.
Okay, so there's your test cases.
Let me show you what your main would look like.
And this is the code that I'm providing for you.
This is the function you have to write, right here it's called
is palindrome expects a std string, returns a boolean.
Right now I'm just returning false.
You have to write this.
And here's the main.
I've got a vector of a bunch of strings, and these
strings are my test cases.
And that's it.
You shouldn't have to do anything in the main.
The main is basically going to loop through all of these strings
and call the is palindrome method right there, pass the string into
it, you'll return true and false, and the main will display it.
So your job is to implement this function right here,
remember, use a deque.
Okay, so have fun.
Think about it. It's actually a pretty simple problem.
And don't go crazy with iterators.
You don't have to use any of that stuff.
Just use the front and the back of the deque, that's what it's all about.
And when you're done, you can come over to challenge one solution
and meet me in the next video.