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

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

Ludisposed · Accepted Answer · 2017-11-02 08:31:08Z

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.

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? — NinjaG
– NinjaG, Commented Nov 1, 2017 at 22:45
@NinjaG See my edited answer, regarding the performance question — Ludisposed
– Ludisposed, Commented Nov 2, 2017 at 17:22

Stack Exchange Network

Palindrome implementations - iterative and recursive

1 Answer 1

Timing

You must log in to answer this question.

Hot Network Questions

Palindrome implementations - iterative and recursive

1 Answer 1

Timing

You must log in to answer this question.

Related

Hot Network Questions