We're back today with another common coding interview question. This week we're going to be writing some code to check if a string is a palindrome. A palindrome is a word or sentence which is read the same backwards as it is forwards, such as the name, "Hannah", or the sentence, "Never odd or even".
Walking Through the Problem
The complexity of this problem depends on whether we have to check a single word or if we also have to check full sentences. In the case of the latter, we have to remove punctuation and spaces, since we only actually care about the letters. We'll start with the simpler version of the problem, and then we'll move onto full sentences.
One thing we have to keep in mind for both versions of the problem is that uppercase and lowercase characters are technically not the same, so we have to be careful to make sure we check letters in the same case.
For this purpose, we can use the casefold method (see documentation). In this post, we're going to assume that all of the strings use basic Latin characters, but there are ways to expand casefold to account for other symbols. I'd recommend taking a look at this StackOverflow answer for more details.
Now that we have these cautionary notes out of the way, how do we actually tackle the problem? As with all questions like this, there are many paths to a solution.
One option available to us is to convert the string to a list. The reason we'd want to do something like this, is that Python lists have a built in reverse method. We could then perform a comparison to the original string with the this new reversed version using ==.
Something to watch out for in this solution is that reverse performs an in-place transformation on the list, so we either need to make a copy of the list for comparison, or we need to convert the list back to a string using join.
We have a more manual option available to us in the form of a for loop. Strings themselves are iterable, so we can check each character against another character one at a time.
We can make use of the enumerate function (details can be found here) to create a counter alongside each character in the string, starting with 1. We can then use this counter to access characters from the other end of the string using negative indices. For example, the character at index -1 is the final character in the string; the item at index -2 is the penultimate character, etc.
One final option we're going to look at is using slices. We have a couple of posts on slices, so if you're not familiar with how slicing works, I'd recommend you take a look at the posts below:
https://blog.tecladocode.com/python-slices/
https://blog.tecladocode.com/python-slices-part-2/
Using Lists and reverse
We're going to start of by looking at the name, Hannah. We know that Hannah is in fact a palindrome, and it also contains a capital letter, which means we can test that our case folding works as expected. We're also going to use a second string, Peter, which is not a palindrome. This is just to test that we don't have erroneous results coming out of our implementation.
Since we're going to be checking multiple strings, we should start by defining a function. We know that we have to pass in a string to test, so we'll create a test_string parameter while we're at it.
def check_if_palindrome(test_string):
pass
Our first step should be to convert test_string into a list, which we're going to call characters. We can then call the reverse method on this new list.
def check_if_palindrome(test_string):
characters = list(test_string)
characters.reverse()
Before we can make this new characters list, however, we have to make use of casefold to get rid of any capital letters in the string that might cause issues with our comparison.
def check_if_palindrome(test_string):
characters = list(test_string.casefold())
characters.reverse()
Now that we have our reversed characters, we can use join to convert the list back to a string, and then we can compare the new reversed string against the case folded original:
def check_if_palindrome(test_string):
characters = list(test_string.casefold())
characters.reverse()
if "".join(characters) == test_string.casefold():
print(f"{test_string} is a palindrome."
else:
print(f"{test_string} is not a palindrome."
If we test our function with "Hannah" and "Peter", we can see that everything works as expected:
def check_if_palindrome(test_string):
characters = list(test_string.casefold())
characters.reverse()
if "".join(characters) == test_string.casefold():
print(f"{test_string} is a palindrome.")
else:
print(f"{test_string} is not a palindrome.")
check_if_palindrome("Hannah") # Hannah is a palindrome.
check_if_palindrome("Peter") # Peter is not a palindrome.
Using a for Loop and enumerate
Once again, we're going to start by defining a function with a single parameter. However, this time, we don't need to do anything with lists, since we'll be iterating over the strings directly.
def check_if_palindrome(test_string):
pass
Our for loop is going to make use of enumerate, which will create a tuple for each character in the test_string, containing a counter and the current character. These tuples get collected in an enumerate object, which is what our for loop will iterate over.
As such, for each iteration, we're going to get a tuple back, which we can unpack into two variables. We talked about this in our recent post on destructuring in Python.
By default, enumerate's counter starts from 0, but we want it to start from 1, since we'll be using this value to access characters using negative indices. The final item in a collection is at index -1, not -0. We can correctly configure the counter by setting the start parameter value to 1.
Just like before, we also have to make sure to remove any capital letters from the strings, so that we're comparing all of the characters in the same case:
def check_if_palindrome(test_string):
for index, letter in enumerate(test_string.casefold(), start=1):
pass
Inside the for loop, we're going to perform a test using an if statement, where we'll compare characters one at a time. The first character of the string will be compared to the final character in the string, and we'll move along the string with each iteration.
We're actually going to be testing if the string is not a palindrome, which will make sense in a moment. If we find a non-matching character, we're going to immediately break, since there's no point checking any of the other characters. We already know the string is not a palindrome.
def check_if_palindrome(test_string):
for index, letter in enumerate(test_string.casefold(), start=1):
if letter != test_string[-index].casefold():
print(f"{test_string} is not a palindrome.")
break
So, why did we do it this way? The reason is that we need every single one of the characters to match before we can say that something is in fact a palindrome. It's not enough for just the first character to match, for example.
If we perform a check for matching characters, instead of non-matching characters, we have to keep track of the fact that all of the characters matched, which is a lot of housekeeping we don't want to have to do.
Instead, we can use a for / else structure. We've written about this previously so take a look if this is new to you.
If we find a non-matching character, we break the loop immediately, so if the for loop runs to completion, it means that all of the characters matched. An else clause attached to a for loop only runs if the loop completed without encountering a break statement or an exception.
We can therefore put our "... is a palindrome." message inside this else clause.
def check_if_palindrome(test_string):
for index, letter in enumerate(test_string.casefold(), start=1):
if letter != test_string[-index].casefold():
print(f"{test_string} is not a palindrome.")
break
else:
print(f"{test_string} is a palindrome."
check_if_palindrome("Hannah") # Hannah is a palindrome.
check_if_palindrome("Peter") # Peter is not a palindrome.
It's very important that the else keyword inline with the for loop definition. It is not part of the if block.
Slices
Possibly the most elegant solution out of all of these options involves the use of slices. Once again, if you're not familiar with slices, read the posts linked earlier. They're an awesome, versatile tool that you'll find uses for everywhere.
The crux of our slice solution is a bit of rather arcane syntax: [::-1]. What this does, is take an entire sequence and reverse it. The best thing about this, and slices in general, is that they don't modify the original collection. This makes our lives very easy.
Our solution is essentially just a single if statement, where we compare two case folded strings.
def check_if_palindrome(test_string):
if test_string.casefold() == test_string[::-1].casefold():
print(f"{test_string} is a palindrome.")
else:
print(f"{test_string} is not a palindrome.")
check_if_palindrome("Hannah") # Hannah is a palindrome.
check_if_palindrome("Peter") # Peter is not a palindrome.
Dealing with Sentences
Now that we've covered a number of solutions for single words, let's consider how to handle full sentences. As was mentioned earlier, we need to get rid of all punctuation and spaces, since we only care about the letters themselves.
Finding all of the letter characters in a string is something we've tackled before in this series on coding interview problems when finding the longest word in a paragraph. I'd recommend you give this post a read, as we cover a lot of the problems associated with a problem like this.
In order to avoid missing some punctuation characters, it was determined that regular expressions were our best bet when trying to find all the letter characters in a string.
Python has a module for dealing with regular expressions called re, so we will need to import it as part of our solution. Specifically, we're concerned with a function called sub, which allows us to replace a pattern with another string. In our case, we'll be replacing all non-letter characters with an empty string, "".
Let's start with our function definition for now:
def check_if_palindrome(test_string):
pass
First we're going to remove all of the uppercase letters from our test_string using the casefold method. We can then pass this new, lowercase string to our sub function.
The sub function is going to allow us to filter out all non-letter characters in the test_string. The RegEx pattern we'll use to accomplish this is [^a-z]+. This looks pretty cryptic, but what it means is match any number of characters that are not the letters a to z. Note that as we already casefolded the test_string we don't need to check for the uppercase versions as well.
import re
def check_if_palindrome(test_string):
letters_only = re.sub("[^a-z]+", "", test_string.casefold())
print(letters_only)
If we pass in even a string full of punctuation, we'll now end up with an entirely lower case string containing only letter characters.
check_if_palindrome("NeVeR! - oDd! - Or! - eVEn!")
# neveroddoreven
Now we can make use of any of our single word solutions, with some minor modifications. We've already case folded all the text, so there's no need to do that going forward:
import re
def check_if_palindrome(test_string):
letters_only = re.sub("[^a-z]+", "", test_string.casefold())
if letters_only == letters_only[::-1]:
print(f"'{test_string}' is a palindrome.")
else:
print(f"'{test_string}' is not a palindrome.")
check_if_palindrome("Never odd or even.")
# 'Never odd or even.' is a palindrome.
check_if_palindrome("Python is awesome!")
# 'Python is awesome!' is not a palindrome.
And that's all there is to it!
Wrapping Up
I actually think this is a really interesting question, particularly when it comes to full sentence palindromes. Hopefully you learnt how to tackle this kind of problem, as well as soon cool new skills, and I really hope you shine in your next coding interview!
If you're really looking to upgrade your Python skills, you should give our Complete Python Course a try! We'd really love to see you on the course!
We also have a form down below for signing up to our mailing list. We post regular discount codes for our courses, so it's a great way to ensure you always get the best deal.
