In this lecture, we'll implement our third algorithm to determine whether a string is a palindrome. In an earlier lecture, we completed the first four steps of the function design recipe. The next step is implementing the body of the function. This algorithm involves comparing pairs of characters. The character at index zero is compared to the character at the last index. The second to the second last. Third to third last. Until the middle of the string is reached. To implement this algorithm, we're going to use two variables to keep track of the indices of the characters to compare. I will initially refer to the first index of the string, and j will initially refer to last index of the string. Here's a picture of this starting situation. This rectangle represents the string. Initially, i refers to index 0, and j to the last index of the string. And those are the first two characters compared. As we progress, i and j move closer to the middle of the string. As we compare these pairs of characters, when we find two characters that are not the same, we can conclude at that point that the string is not a palindrome. Let's start to implement this. We'll use a while it to keep comparing pairs of characters, as long as the character of the string at index i is equal to the character of the string at index j. In the body of the while loop, we are going to increase index i by one to move onto the next character, and decrease index j by one. At this point, our program only stops comparing pairs of characters when it finds two characters that are not the same. But what if we have a palindrome? All of the pairs of characters would be the same. And in that case, we need to stop when the middle of the string is reached. For an odd length string, like racecar, the middle of the string is reached when indices i and j are equal. What about for a string that has an even length, like noon? When we compare these pairs of characters, the last pair of characters to be compared are the ones at index 1 and index 2. I's value would be increased to become index 2, and then j's value would be increased to become index 1. At that point we'd need to stop. So we stop when i and j are next to each other. But j is less than i. So here's the stopping situation for the even case. We stop when j is less than i. So this is for even length strings, and this is for odd length strings. We've determined that the middle of this string is reached when j is less than or equal to i. In other words we want to keep going as long as i is less than j. We'll add this condition to our while loop now. We've almost finished our program. After the while loop has exited, we need to return the appropriate value, either true or false. This return statement is reached when the while loop condition has become false. And there are two reasons why it might be false. The first is that the middle of the string was reached. And the second is that a pair of characters that were not equal to each other was found. If the middle of the string is reached, then the string is a palindrome. If the middle of the string wasn't reached, then the string isn't a palindrome. We know that the middle of the string is reached when i is equal to j, in the odd case, or j is less than i, in the even case. In other words, the middle is reached when j is less than or equal to i. So we'll return that expression. When this expression is true, the middle of the string is reached, and we've found a palindrome. When it's false, the middle of the string hasn't been reached, so we haven't found a palindrome. Now that we've implemented the body of the function, it's time to complete the last step of the function design recipe and test the function. We'll run the module and call the function from the Python shell. We want to confirm that each of the function calls returns a value that we expect, noon and racecar are palindromes. And we want our function to tell us that dented is not.
