1 00:00:05,570 --> 00:00:08,820 Hello, welcome to the section 20, challenge 4 video. 2 00:00:09,770 --> 00:00:11,199 This, you've already seen before. 3 00:00:11,230 --> 00:00:14,079 We did this challenge in challenge 1. 4 00:00:14,450 --> 00:00:17,930 This is where we decided whether a string was a palindrome or not. 5 00:00:18,840 --> 00:00:20,450 We use the deque in challenge 1. 6 00:00:20,450 --> 00:00:23,069 What we're going to use here in challenge 4 is we're going to use a 7 00:00:23,069 --> 00:00:26,240 stack and a queue to do the same thing. 8 00:00:27,110 --> 00:00:29,580 It's actually exactly the same main driver. 9 00:00:29,950 --> 00:00:32,729 The only difference is your function is going to be different obviously, 10 00:00:32,729 --> 00:00:35,579 because it has to use a stack and a queue to solve the problem. 11 00:00:36,219 --> 00:00:39,700 What I would ask you to do is go back to challenge one and play 12 00:00:39,700 --> 00:00:43,000 the description video, where I go into what a palindrome is and so 13 00:00:43,000 --> 00:00:44,739 forth rather than repeat it here. 14 00:00:45,010 --> 00:00:46,849 But if you're here already, and you don't want to go over there, 15 00:00:46,849 --> 00:00:48,419 I'll do a real quick review. 16 00:00:49,030 --> 00:00:52,789 A palindrome is a string that reads the same backwards or forwards, so 17 00:00:52,789 --> 00:00:57,190 we have a couple of examples here, madam, bob, toot, radar, so no matter 18 00:00:57,190 --> 00:00:59,960 how you read it from the left or from the right, it's the same word. 19 00:01:00,740 --> 00:01:04,739 And we can have entire phrases that are palindromes as well. 20 00:01:04,750 --> 00:01:09,139 So, a Toyota's a Toyota, a Santa at NASA, a man, a plan, a cat, a ham, 21 00:01:09,139 --> 00:01:11,270 a yak, a yam, a hat, a canal-panama. 22 00:01:12,299 --> 00:01:14,000 It's amazing that this actually is a palindrome. 23 00:01:14,990 --> 00:01:18,090 For palindrome phrases like this, what we're going to do is we're going to 24 00:01:18,090 --> 00:01:21,880 remove all the spaces, and we're going to remove all the special characters. 25 00:01:22,210 --> 00:01:23,720 And we're going to make those uppercase. 26 00:01:23,940 --> 00:01:28,349 So, in the case of a santa at NASA, what we're going to do is we're 27 00:01:28,350 --> 00:01:30,580 going to create that string from it. 28 00:01:31,010 --> 00:01:34,470 You can see it says ASANTAATNASA right in there, but no spaces, 29 00:01:34,480 --> 00:01:35,449 everything's uppercase. 30 00:01:35,800 --> 00:01:38,260 And if there are any apostrophes or anything else, 31 00:01:38,349 --> 00:01:39,140 we're going to get rid of it. 32 00:01:40,349 --> 00:01:42,319 So, we're only going to process alpha characters. 33 00:01:42,320 --> 00:01:45,479 And you can use the CC type header file for that. 34 00:01:46,570 --> 00:01:47,239 That's it. 35 00:01:48,420 --> 00:01:49,450 Good luck with this one. 36 00:01:49,460 --> 00:01:52,380 Like I said, go back to challenge 1 description, and 37 00:01:52,380 --> 00:01:53,730 I talk a lot more about that. 38 00:01:53,990 --> 00:01:56,670 Actually, let me show you a sample run, so you don't have to go back there. 39 00:01:56,910 --> 00:02:00,320 I'm going to show you a sample run of my solution here. 40 00:02:01,139 --> 00:02:05,559 And I'll build and run the main driver. 41 00:02:05,559 --> 00:02:07,000 I'll show you the code also in a second. 42 00:02:07,020 --> 00:02:10,120 The main driver has a bunch of test cases that they run. 43 00:02:10,680 --> 00:02:13,959 All you have to do is write one function, it's called, is palindrome 44 00:02:13,959 --> 00:02:15,620 and it returns true or false. 45 00:02:15,650 --> 00:02:17,889 I pass you a string, you return true or false. 46 00:02:18,120 --> 00:02:21,980 So, in this case, a is a palindrome, aa is palindrome, 47 00:02:22,760 --> 00:02:23,920 aba is a palindrome and so forth. 48 00:02:23,949 --> 00:02:25,850 Obviously, ab and abc are not. 49 00:02:26,620 --> 00:02:30,700 Radar, and bob, and ana, and avid diva, and there's a Toyota's 50 00:02:30,700 --> 00:02:32,910 a Toyota, a santa at NASA. 51 00:02:33,160 --> 00:02:36,420 C++ is also a palindrome because what we're doing is we're removing the 52 00:02:36,420 --> 00:02:41,269 + +. And just using the capital C, we're getting rid of the special characters. 53 00:02:41,639 --> 00:02:44,829 So, there's some test cases and here you can see the man, the plan, the 54 00:02:44,830 --> 00:02:45,990 cat, and so forth is a palindrome. 55 00:02:47,220 --> 00:02:48,710 You can read it the same both ways. 56 00:02:49,050 --> 00:02:51,100 So, that's the sample run. 57 00:02:51,420 --> 00:02:54,740 And let me show you the main that I'm giving you, this 58 00:02:54,740 --> 00:02:55,719 is the main I'm giving you. 59 00:02:55,719 --> 00:02:59,599 It's the same exact main that I gave you for challenge 1 except what I 60 00:02:59,600 --> 00:03:01,120 want you to do is I want you to use. 61 00:03:01,180 --> 00:03:02,200 You can see right there. 62 00:03:02,620 --> 00:03:04,970 Use a stack and a queue before we use the deque. 63 00:03:05,150 --> 00:03:07,109 So, this will give you a little bit of experience with that. 64 00:03:07,400 --> 00:03:13,369 You can see the main here and all I'm doing in the main is I've got a vector 65 00:03:13,370 --> 00:03:15,790 of strings and those are my test cases. 66 00:03:15,790 --> 00:03:18,130 And I'm just looping through that vector and I'm calling your 67 00:03:18,130 --> 00:03:20,429 function is palindrome right here. 68 00:03:20,430 --> 00:03:22,750 I'm passing in the string and you're returning true or 69 00:03:22,750 --> 00:03:23,989 false, and I'm displaying that. 70 00:03:24,870 --> 00:03:25,960 It's as simple as that. 71 00:03:26,210 --> 00:03:30,210 Here's the function you have to implement, it's called is_palindrome. 72 00:03:30,210 --> 00:03:32,949 It expects the string, and it returns true/false. 73 00:03:32,950 --> 00:03:34,980 Right now, I'm just returning false for everything, 74 00:03:35,290 --> 00:03:36,670 so if you run this right now, you're going to get... 75 00:03:36,670 --> 00:03:39,110 Actually, I'll run it right now, so you can see what it looks like. 76 00:03:39,500 --> 00:03:44,769 If I run this guy right now, it's going to say false all the way 77 00:03:44,889 --> 00:03:47,530 down the line because there's no real logic in that function. 78 00:03:47,849 --> 00:03:50,519 But it all runs, and compiles, and no worries at all. 79 00:03:51,320 --> 00:03:52,280 So, that's it. 80 00:03:52,650 --> 00:03:54,550 If you solve the problem with the deque, you kind 81 00:03:54,550 --> 00:03:55,800 of know how to approach it. 82 00:03:56,320 --> 00:03:57,870 I'm not going to give you any hints here. 83 00:03:57,890 --> 00:04:01,610 If you want a hint or if you have questions, please post in the Q&A, 84 00:04:02,099 --> 00:04:03,540 and I'll be glad to answer them there. 85 00:04:04,230 --> 00:04:05,229 Alright, so good luck. 86 00:04:05,460 --> 00:04:06,739 I'll see you in the next video. 87 00:04:06,740 --> 00:04:08,049 And I'll show you my solution.