1 00:00:05,340 --> 00:00:08,410 Okay, so welcome back to the stl challenge 1 solution. 2 00:00:08,910 --> 00:00:12,179 I'm in section 20, and I'm in the challenge 1 solution project. 3 00:00:12,509 --> 00:00:16,229 And this is the project where we had to write the is palindrome function. 4 00:00:16,570 --> 00:00:19,720 So hopefully, you were able to solve this problem. 5 00:00:19,720 --> 00:00:23,439 It's actually quite simple when you think about it, so let's talk about it. 6 00:00:24,320 --> 00:00:26,949 The idea is -- we're going to use a deque. 7 00:00:26,960 --> 00:00:33,290 So the idea is let's say that we have a string like aabaa, that's 8 00:00:33,299 --> 00:00:34,839 obviously a palindrome, right. 9 00:00:34,840 --> 00:00:36,940 It reads the same from the front or from the back. 10 00:00:37,240 --> 00:00:39,570 So what we -- then that's coming in here is my string. 11 00:00:39,810 --> 00:00:42,170 So what I want to do is I want to create this deque 12 00:00:42,180 --> 00:00:43,460 of characters right here. 13 00:00:43,980 --> 00:00:48,160 And I just want to push these characters into the deque. 14 00:00:48,219 --> 00:00:49,970 So I'm going to grab that, and I'm going to push back. 15 00:00:49,970 --> 00:00:52,789 So I'm going to basically create a deque that looks like this. 16 00:00:54,209 --> 00:00:55,750 I'm going to push the characters onto the deque. 17 00:00:56,280 --> 00:00:58,110 And then what I'm going to do is I'm going to check the front 18 00:00:58,110 --> 00:01:00,980 of the deque and I'm going to check the back of the deque, grab 19 00:01:00,980 --> 00:01:02,249 whatever's there compare them. 20 00:01:02,679 --> 00:01:06,749 If they are the same, then I process them, remove them and 21 00:01:06,750 --> 00:01:10,269 move on to the next ones, right. 22 00:01:10,279 --> 00:01:11,049 Compare them. 23 00:01:11,059 --> 00:01:12,600 If they're the same, I'm going to remove them. 24 00:01:13,170 --> 00:01:18,070 At that point, if I end up with an empty deque or a deque with just one item 25 00:01:18,070 --> 00:01:22,579 in it, then i know it's a palindrome, it's as simple as that for something 26 00:01:22,590 --> 00:01:27,789 like, let's say, 4 so I'm going to grab that string, put it into the deque. 27 00:01:28,129 --> 00:01:30,379 I'm going to grab the first character here in the front. 28 00:01:30,389 --> 00:01:32,750 I'm going to grab the last character here in the back. 29 00:01:32,990 --> 00:01:34,350 They are not equal. 30 00:01:34,350 --> 00:01:37,626 So there's no way this can be a palindrome. So I'm out right there. 31 00:01:38,420 --> 00:01:40,720 Okay, so let's walk through the actual code. 32 00:01:40,720 --> 00:01:43,220 So now you know the algorithm is pretty straightforward. 33 00:01:43,220 --> 00:01:44,820 So let's look at the code right here. 34 00:01:46,220 --> 00:01:48,220 Here's the is palindrome function. 35 00:01:48,720 --> 00:01:51,490 And I've got a deque, and I'm initializing it to an empty 36 00:01:51,490 --> 00:01:52,680 deque, I'm just calling it d. 37 00:01:53,440 --> 00:01:58,600 Then for each character in this string s, if the character is an 38 00:01:58,610 --> 00:02:01,389 alpha, right, so in other words it's not white space, it's not a 39 00:02:01,400 --> 00:02:03,160 digit, it's not special characters. 40 00:02:03,349 --> 00:02:06,340 So if it's if it is alpha, then what I'm going to do is I'm going 41 00:02:06,340 --> 00:02:10,570 to convert it to uppercase and push it onto the deque in the back. 42 00:02:11,730 --> 00:02:12,190 That's it. 43 00:02:12,380 --> 00:02:15,749 So once this loop is done, whatever was in this string is now in the 44 00:02:15,750 --> 00:02:20,090 deque minus the special characters and the white space and everything else. 45 00:02:20,480 --> 00:02:20,940 That's it. 46 00:02:21,280 --> 00:02:23,839 Now I've got two variables here c1 and c2. 47 00:02:24,209 --> 00:02:27,150 Those are the variables that I'm using to store what I'm reading from the 48 00:02:27,150 --> 00:02:28,880 front and from the back of the deque. 49 00:02:29,680 --> 00:02:31,310 And now I'm going to do something right here. 50 00:02:31,310 --> 00:02:32,170 This is my loop. 51 00:02:32,179 --> 00:02:33,069 It's really simple. 52 00:02:33,429 --> 00:02:36,919 While the size of the deque is greater than 1, then I want to keep processing. 53 00:02:37,150 --> 00:02:39,720 Once I hit 0 or 1, I'm done, right. 54 00:02:39,720 --> 00:02:41,109 It's got to be a palindrome. 55 00:02:41,520 --> 00:02:45,380 So I'm asking the deque, okay, give me your front element, 56 00:02:45,630 --> 00:02:49,130 give me your back element, and I'm storing those in c1 and c2. 57 00:02:49,610 --> 00:02:52,209 I'm getting rid of those two elements from the deque. 58 00:02:52,210 --> 00:02:53,189 I don't need them there. 59 00:02:54,120 --> 00:02:55,079 And then I'm comparing them. 60 00:02:55,259 --> 00:02:58,900 So if c1 is not equal to c2, then the characters can't be the same. 61 00:02:58,900 --> 00:03:00,470 There's no way this can be a palindrome. 62 00:03:00,470 --> 00:03:02,070 So I'm returning false immediately. 63 00:03:02,730 --> 00:03:04,600 If I get through the loop, I'm returning true. 64 00:03:04,600 --> 00:03:05,950 It's got to be a palindrome. 65 00:03:06,540 --> 00:03:08,130 So that's it that's the solution. 66 00:03:08,650 --> 00:03:12,270 And as i said, this is a very common problem given in a coding interview. 67 00:03:12,599 --> 00:03:16,249 And what the interviewer wants is for the applicant to try to 68 00:03:16,250 --> 00:03:20,510 solve it a different way and then say oh by the way, can you solve 69 00:03:20,510 --> 00:03:22,640 it using a deque, and that's it. 70 00:03:23,120 --> 00:03:25,170 So you can see it's a real simple solution. 71 00:03:25,540 --> 00:03:28,540 No iterators, nothing fancy, no algorithms. 72 00:03:28,540 --> 00:03:31,430 You're just using the front and the back of the deque, 73 00:03:31,730 --> 00:03:32,880 just like we're supposed to. 74 00:03:32,990 --> 00:03:34,839 All right, so I hope you enjoyed this challenge.