In this lecture we'll implement our second algorithm for determining whether a string is a Palindrome. As before we start with the same results we follow in our design recipe as we did for the last lecture. So our second algorithm we split this string into two halves. Reverse the second half. And then compare that reversed second half to the first half. Again, we need to reverse a string, so let's go get that code from the previous version. As a quick reminder, if I have an even length string, then I'm going to divide this in half, reverse the second half, and then compare it to the first half. I'm going to write some indices at the top, 0, 1, 2 and 3. If I have an odd length string on the other hand, such as a race car, my approach is to not include the E and just reverse everything after the E. That should give me RAC, which I then compare to the first half, and again I'm going to write the indices of each letter above. The last example that we have is, dented, split that into half, reverse the last half and then unsuccessfully compare the, the reversed second half to our first half. And now it's time to play with indices because we need to know exactly where we're going to slice in each string. The length of noon is 4, 4 divided by 2 is 2, so that tells us the index to, to slice from for, to get the second half of this strip, 4 divided by 2. The length of race car is 7. 7 divided by 2, well, if I just do straight division, then that gives me 3 and a half. But, if I do integer division, then that gives me 3. So 3 is the number of characters in each half, but I don't want to include the e there. So, I would, I'm going to have to figure out how to work around this, with my slicing perhaps. I can take some and subtract 7 divided by 2, 7 divided by 2 is 3, thus we got a slash there, sorry, 7 minus 7 divided by 2 that gives me 4, which is the first index of the character that I want. Now is that going to work over here, 4 minus 4 integer division 2. Well 4 integer division 2 is 2, 4 minus 2 is 2 and indeed, that gives me the index that I need in order to start the slice to grab the second half of the string. In general then the links of the string divided by two, that gives me the number of characters for each slice. I can use this result as the, the last index in a slice, then, in order to grab the first half of the string, and I can take the, the length of s minus this value. In order to find the index of the first character in the second half to graph. So over here, 7 minus 7 divided 2, gave me 4, and that is indeed the index over the first character in the second half that I want to reverse. We're done thinking hard. We know that the first half that we want to grab, is everything up to the length of s divided by 2, and we know that we want to grab the, everything from the length of s minus the length of s, divided by 2, for the second half. And that we want to reverse the second half and check to see if it's equal to the first half. That's a little bit convoluted because we have a whole bunch of repetitions of length of s. So I am going to have one separate step where I grab that length, and make it so that we only have to do that calculation once. I think the code is a little bit clearer this way. Your opinion may differ. Getting rid of the scribbles. We're just going to add a couple of comments we're so that other people who might be reading this code later can understand what we were doing, n is the number of characters in s. And here what we're doing is we are comparing, the first half of s, to the reverse of the second path, because we so painfully figured out that we were omitting the middle character in an odd length string. Let's actually mention that. All that's left now is for us to test. Try noon, and looks good so far. How about racecar, yup, that's also good. And last, dented. Good. We're done.
