Palindrome implementations - iterative and recursive

Question

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()

• Ludisposed: Your UnitTests fail, because there is no function: is_palindrome

Answer 1

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
 This function hadles it iteravely"""
 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
 This function hadles it recursively"""
 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("Your iter: {}".format(min(timeit.Timer('is_palindrome_iterative(s)', setup=setup).repeat(7, 1000))))
 print("My iterative: {}\n".format(min(timeit.Timer('is_palindrome_iter(s)', setup=setup).repeat(7, 1000))))
 print("Your recursive: {}".format(min(timeit.Timer('is_palindrome_recursive(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
Your recursive: 0.03150451902264695
My recursive: 0.021585517111614272
Shortest: 0.004582702402422756

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.

• NinjaG: I was wondering if remove_punctuation_and_lower(text) may add a lot of overhead that will dramatically decrease the code performance from the perspective of both memory and time?
• Ludisposed: @NinjaG See my edited answer, regarding the performance question