How would you check if a string is a palindrome?

A palindrome is a word, phrase, number, or other sequences of characters that reads the same backward as forward, ignoring spaces, punctuation, and capitalization.

One way of checking whether a string is palindrome or not is by comparing the characters at each end of the string and work your way towards the middle of the string. If the characters match for each comparison, then the string is a palindrome. Here is a simple Python function for checking if a string is a palindrome.

def is_palindrome(s):
    # Convert string to lowercase, remove non-alphanumeric characters
    s = ''.join(c for c in s.lower() if c.isalnum())
    return s == s[::-1]

print(is_palindrome("A man, a plan, a canal: Panama"))  # returns True
print(is_palindrome("race a car"))  # returns False

If you want a more manual implementation without the use of python’s built-in methods, you could also do:

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

where ‘i‘ is the starting index and ‘j‘ is the last index of the array. The condition part of the loop will make the function to return ‘false‘ as soon as the comparison fails and ‘true‘ if both the parts are successfully same after full comparison of ‘i‘ from start and ‘j‘ from the end.

For example:

When you input: ‘is_palindrome("MADAM")‘, in the first iteration, ‘s[0] (’M’)‘ compares with ‘s[4] (’M’)‘ which are equal and then ‘s[1] (’A’)‘ with ‘s[3] (’A’)‘, so after full comparison it returns ‘true‘ as they are a palindrome.

When you input: ‘is_palindrome("Hello")‘, in the first iteration, ‘s[0](’H’)‘ compares with ‘s[4](’o’)‘ which are not equal so at the first comparison it returns ‘false‘ as they are not a palindrome.

The purpose of ‘len(s)//2‘ is to avoid over-checking in palindromes with an odd number of characters. This makes the solution efficient with the time complexity of O(N), where N is the length of the string. No additional space is used, making the space complexity O(1).

The Python ‘[::-1]‘ does a complete slice over the string in reverse, i.e., the string is completely reversed which allows us to do a equality check on the original and reverse string. This is another clever technique to identify a palindrome in Python though it doesn’t really show the manual process of comparing character by character from either end towards the center. The time complexity also remains O(N).