Exercise: Palindromes

Inside the directory you created for this course on Python, create a new folder called Exercise-7-Palindromes and put the .py solution files for this exercise within it.

The function we'll create will take in a string value and output True if it is a palindrome, or otherwise False. Based on the return value of this function, we could then make the desired output.

First, let's get settled on the naming for the function.

We'll call the function is_palindrome(), since it checks whether a string 'is a palindrome', or not. The argument it'll take (which is a string) could simply be called s.

def is_palindrome(s):
    # more code to come here
    pass

The keyword pass is used here just to make sure that the body of the function is not empty, since an empty function body throws an error. Later on, we'll remove this.

With the naming out of the way, next we think on the logic of the function.

We need to go only as far as half the length of the string to determine whether it's a palindrome or not.

Alright, so I need to know the length of the string in the solution. Let's create a variable for it.

This is how you should approach programming problems. As soon as you come up with a solution to a problem in your mind, you should break it into simpler individual subproblems that you would need in order to implement it.

In this case, the subproblem is to figure out the length of the given string.

Coming back to the exercise, we'll create a local variable n to denote the length of the string.

def is_palindrome(s):
    n = len(s)
    # more code to follow

The idea is that we need to go upto half the length of the string and compare each character from the left with the corresponding character from the right.

If in any comparison, we find out that the characters being compared are not the same, we could immediately say that the given string is not a palindrome i.e return False.

Which concept in Python does this, as a whole, remind of?

We need to iterate upto half the length of the string, likewise we need to use a loop to accomplish this.

But which loop to use: for or while?

Technically, we could use any of these. But for now, we'll go with for because setting it up is easier compared to while.

Recall that the for loop iterates over a given sequence. In this case, the sequence can't be the string itself, since we don't need to iterate over the whole string — just a small part of it.

The other option is to iterate over the sequence defined by range().

But how do we know what to pass to range()?

We do a bit of thought work in our mind.

If we have a string with an even number of characters, we need to go as far as half of its length. For example, given the string 'deed', its length is 4 which is even, hence we ought to go as far as the second (4 / 2 = 2) character in the string.

Unfortunately, we can't pass n / 2 to range(). This is because range() only accepts integers, and n / 2 is never an integer. n / 2 uses the normal division operator in Python, which always returns a float (even if the result is an integer).

Any other options?

Let's try the floor division operator — //. It floors its result and always returns an integer. Seems convincing!

Why not consider a few strings and see whether n // 2 takes us as far as is required:

1. In a string of length 2 — such as 'aa' — we need to do 1 comparison, and n // 2 is 1.
2. In a string of length 4 — such as 'deed' — we need to do 2 comparisons, and n // 2 is 2.
3. In a string of length 6 — such as 'denned' — we need to do 3 comparisons, and n // 2 is 3.

Perfect!

Let's now think about odd-length strings.

Let's first see exactly how far do we need to go in an odd-length string.

Suppose we have the string 'ada'. It turns out that we need to go only as far as the first character to determine whether 'ada' is a palindrome or not. If the highlighted parts in 'ada' are the same, the string is a palindrome.

There is no need to compare the letter 'd'. The middle character in an odd-length string would anyways be compared against itself, hence it's better to skip this step.

As before, we'll consider a few strings and see whether n // 2 takes us as far as is required:

1. In a string of length 3 — such as 'ada' — we need to do 1 comparison, and n // 2 is 1.
2. In a string of length 5 — such as 'dioid' — we need to do 2 comparisons, and n // 2 is 2.
3. In a string of length 7 — such as 'racecar' — we need to do 3 comparisons, and n // 2 is 3.

Perfect! The // operator works just as desired.

So, to summarise, the for loop iterates over the sequence defined by range(n // 2).

def is_palindrome(s):
    n = len(s)
    
    for i in range(n // 2):
        # code goes here
        pass

Inside the loop, we compare s[i] with the corresponding character from the end of the string. This character from the string's end is at the index n - i - 1.

In the comparison, if the characters are not the same, it means that the string is definitely not a palindrome; hence, we return False (without completing the loop).

However, when the string is actually a palindrome, this conditional never gets executed, which means that the loop goes to completion. At this point, the statement following the loop is executed. Likewise, we return True here to say that the string is a palindrome.

All this is summarised as follows:

def is_palindrome(s):
    n = len(s)
    
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            return False

    return True

With the function is_palindrome() created, we now just need to call it on the value input by the user, and print 'Yes' if it returns True, or otherwise 'No'.

def is_palindrome(s):
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            return False
    return True


s = input('Enter a word: ')

if is_palindrome(s):
    print('Yes')
else:
    print('No')

First, in line 9, we receive input from the user, put that into the variable s, and then call is_palindrome() on it. If the function returns True, the body of if gets executed, printing 'Yes'; otherwise the body of else gets executed, printing 'No'.

This completes our exercise.

In the exercise above, we could've used a for loop directly to solve the task without having to encapsulate it inside a function. So then why did we use a function?

Well, a function has a couple of advantages.

1. Firstly, we could reuse it in any other place where we ought to perform a palindrome check.
2. Secondly, with a function, we could perform as many palindrome checks as we want to, without having to rewrite the logic of the check.
3. Moreover, as we shall see later on when we consider how to implement this solution directly in a loop (without encapsulating it inside a function), it's easier to implement a palindrome check using a function.