# Palindrome implementations - iterative and recursive

I got asked this palindrome question when the interviewer wants to make sure that my palindrome can check if "Taco! Cat!" is a palindrome. In this example, my palindromes implementation needs to handle with complex examples, like white space, punctuation and mixed letter casing is_palindrome('Taco? Cat.') returns True.

def ascii_letters(text):
#Helper method, it return true if all characters in the string are alphabetic
# (if the string is an uppercase or lowercase letter from A to Z)
# otherwise it will return False (the string contains any non-letter character)
string.ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
string.ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
string.ascii_letters = string.ascii_lowercase + string.ascii_uppercase
for index in text:
if index in string.ascii_letters:
return True
return False
def is_palindrome_iterative(text):
# implement the is_palindrome function iteratively here
# to verify that my iterative implementation, must pass all tests
# First, set up the first_index and
# last_index as the length of array -1
# Inside each iteration, compared the 2 pointers, and see if it's a palindrome
# to handle the different casing and punctuation:
# Called the helper function checks if index is ascii_letters or alphabetic
first_index = 0
last_index = len(text) - 1

# checking the valid condition for the range
while(first_index <= last_index):

left = text[first_index]
right = text[last_index]
while not ascii_letters(left):
first_index += 1
if first_index > len(text) - 1:
return True
# check if the first pointer is not alphabetic or ascii_letters
while not ascii_letters(right):
last_index -= 1
if last_index < 0:
return True

# if the pointer are not the same, return false
if(left.lower() != right.lower()):
return False
first_index += 1
last_index -= 1
return True

def is_palindrome_recursive(text, first_index=None, last_index=None):
# implement the is_palindrome function recursively here
# to verify that your iterative implementation passes all tests
# First, we have the first_index and last_index as None
# set the index for the 2 pointer
# Inside the recursion, compared the 2 pointers, which check if it's a palindrome
# return fales
# to handle the different casing and punctuation:
# Called the helper function checks if index is ascii_letters or alphabetic
if first_index is None or last_index is None:
first_index = 0
last_index = len(text) - 1
# Base Cases
if first_index >= last_index:
return True
# Check letters
left = text[first_index]
right = text[last_index]
update_left = first_index + 1
update_right = last_index - 1
# check if the left pointer is not alphabetic or ascii_letters
# if not, update the left pointer
if not ascii_letters(left):
return is_palindrome_recursive(text, update_left, last_index)
# check if the right pointer is not alphabetic or ascii_letters
# If not, update the right pointer
if not ascii_letters(right):
return is_palindrome_recursive(text, first_index, update_right)

# Check if the left and right pointers are not the same
# Not same, return false
if(left.lower() != right.lower()):
return False

return is_palindrome_recursive(text, update_left, update_right)


I include all the test cases that my code passes:

#!python

from palindromes import is_palindrome
import unittest

class PalindromesTest(unittest.TestCase):

def test_is_palindrome_with_whitespace_and_mixed_casing(self):
# palindromes with whitespace and mixed letter casing
assert is_palindrome('B b') is True
assert is_palindrome('No On') is True
assert is_palindrome('Dog God') is True
assert is_palindrome('Taco Cat') is True
assert is_palindrome('Race Car') is True
assert is_palindrome('Race Fast Safe Car') is True

def test_is_palindrome_with_whitespace_and_punctuation(self):
# palindromes with whitespace and punctuation
assert is_palindrome('B-B') is True
assert is_palindrome('no, on!') is True
assert is_palindrome('dog god?') is True
assert is_palindrome('taco? cat.') is True
assert is_palindrome('race-car!!!') is True
assert is_palindrome('race fast, safe car...') is True

def test_is_palindrome_with_mixed_casing_and_punctuation(self):
# palindromes with whitespace, punctuation and mixed letter casing
assert is_palindrome('No, On!') is True
assert is_palindrome('Dog God?') is True
assert is_palindrome('Taco? Cat.') is True
assert is_palindrome('Race-Car!!!') is True
assert is_palindrome('Race Fast, Safe Car...') is True
assert is_palindrome('Was it a car or a cat I saw?') is True
assert is_palindrome("Go hang a salami, I'm a lasagna hog.") is True
assert is_palindrome('A man, a plan, a canal - Panama!') is True

def test_is_palindrome_with_non_palindromic_strings(self):
# examples of non-palindromic strings that should be rejected
assert is_palindrome('AB') is False  # even length
assert is_palindrome('ABC') is False  # odd length
assert is_palindrome('AAB') is False
assert is_palindrome('AABB') is False
assert is_palindrome('AAABB') is False
assert is_palindrome('AAABBB') is False
assert is_palindrome('ABCZBA') is False
assert is_palindrome('ABCCZA') is False
assert is_palindrome('ABCCBZ') is False
assert is_palindrome('ABCDZCBA') is False
assert is_palindrome('ABCDDZBA') is False
assert is_palindrome('ABCDDCZA') is False
assert is_palindrome('ABCDDCBZ') is False
assert is_palindrome('AAAAZAAA') is False
assert is_palindrome('AAAAAAAZ') is False

if __name__ == '__main__':
unittest.main()

• Your UnitTests fail, because there is no function: is_palindrome Commented Nov 1, 2017 at 8:14

Stuff that could be improved upon:

• Include the import string (You use it but currently not in the question)
• Seperation of control. Don't let the is_palindrome_iter and is_palindrome_recursive do the punctuation removal. What if you want to check for case sensitive palindromes?
• You use string.ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz' but string.ascii_lowercase is already that. Thus this line is totally unnecessary
• Don't use blockquotes as docstrings!, But use an actual docstring
• You can use string slicing in the recursive function
• Ofcourse the easiest way to handle palindromes are just checking if the text == text[::-1]

Code changes, plus addes some extra

import string
import timeit

def is_palindrome_iter(text):
"""Returns True if palindrome

text = remove_punctuation_and_lower(text)
first_index, last_index = 0, len(text) - 1

while(first_index <= last_index):
if(text[first_index] != text[last_index]):
return False

first_index += 1
last_index -= 1

return True

def is_palindrome_rec(text):
"""Returns True if palindrome

if len(text) <= 1:
return True

if text[0] != text[-1]:
return False

return is_palindrome_recursive(text[1:-1])

def remove_punctuation_and_lower(text):
""""Removes punctuation and lower the text"""
return ''.join([i for i in text.lower() if i in string.ascii_letters])

def is_palindrome(text):
"""Simplest way to check for a palindrome"""
text = remove_punctuation_and_lower(text)
return text==text[::-1]

def palindrome_recursive(text):
"""Strip the punctuation adn check for recursive palindrome"""
text = remove_punctuation_and_lower(text)
return is_palindrome_rec(text)


# Timing

As requested the timing of your palindrome functions compared to mine

def timing():
setup = """s = 'A man, a plan, a canal - Panama!'
from __main__ import is_palindrome_iterative, is_palindrome_iter, is_palindrome, palindrome_recursive, is_palindrome_recursive"""
print("My iterative: {}\n".format(min(timeit.Timer('is_palindrome_iter(s)', setup=setup).repeat(7, 1000))))
print("My recursive: {}\n".format(min(timeit.Timer('palindrome_recursive(s)', setup=setup).repeat(7, 1000))))
print("Shortest: {}".format(min(timeit.Timer('is_palindrome(s)', setup=setup).repeat(7, 1000))))


With result:

Your iter: 0.023102631285895847
My iterative: 0.006382375491678111


As you can see, my solution are faster compared to yours, so we can assume it is better in terms of performance. If you really want to have the fastest solution text == text[::-1] wins by a long shot. That is because, string comparison will use compiled C implementation. Instead of the python loop which is a lot slower.