1 00:00:05,420 --> 00:00:08,480 Okay, welcome to the Section 20, Challenge 4 – Solution. 2 00:00:09,260 --> 00:00:13,110 This is the challenge where we're trying to determine whether a string is 3 00:00:13,110 --> 00:00:15,149 a palindrome using a stack and a queue. 4 00:00:15,650 --> 00:00:18,569 So, before I go into the code, let's talk about the process 5 00:00:18,590 --> 00:00:19,920 that we can use to do this. 6 00:00:20,360 --> 00:00:24,690 Suppose we have a word like RADAR, that's the string, 7 00:00:24,740 --> 00:00:26,460 obviously, that is a palindrome. 8 00:00:26,929 --> 00:00:29,620 What we can do is we can have a queue over here, and we 9 00:00:29,620 --> 00:00:31,019 can have a stack over here. 10 00:00:31,960 --> 00:00:35,630 We can take these letters and push them to the queue. 11 00:00:35,820 --> 00:00:41,320 So, it's going to be the r, the a, the d, the a, and the r, 12 00:00:41,320 --> 00:00:42,589 that's the order we're putting them in. 13 00:00:42,830 --> 00:00:44,690 So, this is the front of the queue here. 14 00:00:45,380 --> 00:00:48,279 And then we can take the same word and push it on the stack. 15 00:00:48,469 --> 00:00:54,460 So, in this case, we've got r, a, d, a, r, 16 00:00:54,570 --> 00:00:56,010 so I think you know what's happening now. 17 00:00:56,220 --> 00:00:58,930 This is the top of the stack, this is the front of the queue. 18 00:00:59,269 --> 00:01:03,670 What we can do is we can take those elements and compare them. 19 00:01:04,830 --> 00:01:06,560 If they're the same, we can knock them off. 20 00:01:07,349 --> 00:01:08,559 Then we can go to the next one. 21 00:01:08,969 --> 00:01:11,089 If they're the same, we move on to the next one. 22 00:01:12,850 --> 00:01:14,730 And as you can see, it's pretty easy, right. 23 00:01:15,480 --> 00:01:16,560 At the end, we're done. 24 00:01:17,380 --> 00:01:19,445 If everything matched, we've got a palindrome. 25 00:01:19,445 --> 00:01:23,240 So, that's it, let's take a look at another example. 26 00:01:24,070 --> 00:01:29,059 So, let's say that the word is rear, r, e, a, r, obviously, 27 00:01:29,059 --> 00:01:30,159 that is not a palindrome. 28 00:01:30,409 --> 00:01:33,660 So, we can have our queue over here and we can have our stack over here. 29 00:01:34,140 --> 00:01:36,200 And what we'll do is we 'll, in queue, rear. 30 00:01:36,200 --> 00:01:40,989 So, it's r, e, a, r, this is the front. 31 00:01:41,789 --> 00:01:43,730 And then we'll push rear onto the stack. 32 00:01:43,730 --> 00:01:44,489 So, again, we'll say. 33 00:01:44,490 --> 00:01:46,249 And I'll separate those, so make clear. 34 00:01:46,559 --> 00:01:52,539 R, e, a, r, we'll look at the front of the queue and the top of the stack, 35 00:01:52,590 --> 00:01:54,070 they match, so we can get rid of those. 36 00:01:54,790 --> 00:01:57,639 Then we'll look at the front of the queue, top of the stack, they don't 37 00:01:57,670 --> 00:01:59,179 match, that's not a palindrome. 38 00:01:59,889 --> 00:02:01,589 Okay, so that's it, that's the solution. 39 00:02:01,610 --> 00:02:02,710 It's pretty straightforward. 40 00:02:02,870 --> 00:02:04,230 Now let's see how we do this in code. 41 00:02:05,750 --> 00:02:06,840 Here is the function. 42 00:02:08,430 --> 00:02:10,070 And let me walk you through it really quickly. 43 00:02:10,410 --> 00:02:12,980 So, what I'm doing here is I'm using a range based for loop 44 00:02:13,380 --> 00:02:16,320 to iterate over that string s that's being passed into me. 45 00:02:16,960 --> 00:02:20,470 And for each character, I'm checking is it an alpha character, I'm 46 00:02:20,470 --> 00:02:21,880 not interested in anything else. 47 00:02:22,369 --> 00:02:24,370 If it is, I'm converting it to uppercase. 48 00:02:25,170 --> 00:02:28,060 I'm pushing it on the queue, and then pushing it on the stack. 49 00:02:28,080 --> 00:02:31,440 That's it, that's going to set up those two data structures, so that 50 00:02:31,440 --> 00:02:32,830 I can process them easily now. 51 00:02:33,610 --> 00:02:38,209 Now I'll scroll up and there's the rest of the code, you can see that I've got 52 00:02:38,250 --> 00:02:42,469 two variables here, c1 and c2, that's where I'm reading the characters into. 53 00:02:42,900 --> 00:02:46,240 And all iI'm doing is while the queue is not empty, I could have 54 00:02:46,240 --> 00:02:47,350 used the stack as well here. 55 00:02:47,350 --> 00:02:50,489 It doesn't really matter because they both have the same number of elements. 56 00:02:50,870 --> 00:02:54,600 So, while the queue is not empty, I'm assigning the front of the queue 57 00:02:54,600 --> 00:02:58,040 to c1, and then I'm getting rid of that character from the queue. 58 00:02:58,609 --> 00:03:04,080 I'm assigning the top of the stack to c2 and I'm popping that off the stack. 59 00:03:04,870 --> 00:03:06,500 Then I'm comparing the two characters. 60 00:03:06,750 --> 00:03:08,530 If they're not the same, I'm out. 61 00:03:08,679 --> 00:03:09,990 It's not a palindrome. 62 00:03:10,670 --> 00:03:13,009 When I finish this, if I loop, and everything is done. 63 00:03:13,009 --> 00:03:15,359 And I've got, I've processed all the characters, it must be 64 00:03:15,380 --> 00:03:16,829 a palindrome, I return true. 65 00:03:18,190 --> 00:03:22,270 That's it, and we'll run it just to be, let's build and run. 66 00:03:23,000 --> 00:03:24,679 And there you go, those are the results. 67 00:03:24,700 --> 00:03:29,220 You can see the a is true, the aa is true, abc here is false. 68 00:03:29,580 --> 00:03:31,570 A bunch of these phrases are true. 69 00:03:31,610 --> 00:03:33,969 And then obviously, this is a palindrome, and palindrome are 70 00:03:33,969 --> 00:03:36,070 not palindrome, so we get a false. 71 00:03:36,650 --> 00:03:39,369 So, that's it, you can see a whole bunch of different ways to 72 00:03:39,650 --> 00:03:41,590 solve this palindrome problem. 73 00:03:41,790 --> 00:03:43,120 We did it with a deque earlier. 74 00:03:43,140 --> 00:03:44,579 We did it with a stack and a queue now. 75 00:03:44,580 --> 00:03:46,080 And there's other solutions as well. 76 00:03:46,500 --> 00:03:48,000 So, I hope you had fun doing this. 77 00:03:48,240 --> 00:03:52,009 You can see that using stacks, and queues, and deques, and 78 00:03:52,010 --> 00:03:54,899 all kinds of data structures are pretty fun actually. 79 00:03:55,360 --> 00:03:56,970 Alright, so I'll see you in the next video.