You're familiar with several of Python's types including strings, lists, tuples, and dictionaries. You also know how to use a variety of operations, methods, conditional statements, and loops. This lecture isn't about learning any new Python features. It's about solving a problem by exploring several approaches to it and using what you already know. In this lecture, we're going to focus on a single problem. The problem is determining whether a string is a palindrome. A palindrome is a string that is read the same from front to back and back to front. For example, noon and racecar are both palindromes. Before we start to write any code, we need to decide which approach we'll take to solve this problem. We're going to explore several different approaches for determining whether a string is a palindrome. These approaches are called algorithms. An algorithm is a sequence of steps that accomplish a task. For our first approach, we revisit the definition of palindrome. A palindrome is string that is read the same from front to back, and back to front. That means that if we have a string, and we reverse it, it's a palindrome, if the original and the reverse are the same. Let's consider a couple of examples. The first example is noon. Noon, reversed. We're beginning with the last letter in the original, becoming the first letter in the reverse string, and so on. The original string and the reverse string are the same so this is a palindrome. Next, let's look at racecar. We'll begin by reversing the string, the r becomes the first letter followed by a, and the original string and the reverse string are equal, so this is also a palindrome. One more example, dented. We begin by reversing the string d, followed by e. This time, the 2 strings are not the same so this is not a palindrome. Now, we'll take a different approach to solving the same problem. We're going to start this time by splitting the string into 2 halves. We'll then reverse the second half of the string, so o, n will become n, o. We compare the first half of the original string with the second half reversed. If they're the same, the string is a palindrome. We'll do this again for racecar. Racecar has an odd length. So, it's not clear which half the e should belong in. We're actually not going to include it in either. We're going to take the string, half of the string before e and the other half of the string after e, and omit the e altogether. We'll then reverse the second half getting r, a, c and compare the first half of the original with the second half reversed to confirm that it's a palindrome. Finally, we'll do the same thing for dented. We split the string in half, reverse the second path, compare the first half to the second half reversed, and this time they're not the same, so this is not a palindrome. Let's consider one more approach. In this approach, we're going to compare pairs of characters. We'll start by comparing the first character to the last to see whether they're the same. Then, we'll compare the second character to the second last, and we stop when we reached the middle of the string. If all of the pairs of characters are the same, then the string is a palindrome. Let's do the same thing for racecar. We begin by comparing the first character to the last, then the second to the second last, third to the third last, stopping when we reach the middle of the string. All of the pair, pairs of characters are the same, so this is also a palindrome. And finally, dented. In this case, the first two pairs of characters are the same, but the third character is not the same as the third last so this is not a palindrome. There may be other approaches to solving this problem. But these are three that we thought of. In upcoming lectures, we'll discuss some features of algorithms that might make one more desirable than another. For now though, we'll implement all three of these algorithms. Now, let's follow the steps of the function design recipe to implement this function. I'm going to open a new window in which to write the function definition. The first step of the function design recipe involves writing example calls on the function in the doc string. To do this, we need to give the function a name. I'm going to call it, is palindrome. The function will take one string argument, such as noon, and return a Boolean indicating whether that string is a palindrome. In this case, it returns true. It should also return true for the string racecar. And we expect that when is palindrome is call, called with the argument dented, that it will return false. Next, we'll write the type contract. This function takes one string and returns a Boolean. The third step of the function design recipe is writing the header. We're using name is_palindrome, and we need to give a name now to the parameter to this function. I'm going to call it s. The last part of the doc string is the description. This function should return true if and only if s is a palindrome. The last two steps of the function design recipe involve writing the body of the function and then testing the function. We are going to complete those two steps in an upcoming lecture.
