What possible improvements can be made to a palindrome program?

Question

I am just learning programming in Python for fun. I was writing a palindrome program and I thought of how I can make further improvements to it.

First thing that came to my mind is to prevent the program from having to go through the entire word both ways since we are just checking for a palindrome. Then I realized that the loop can be broken as soon as the first and the last character doesn't match.

I then implemented them in a class so I can just call a word and get back true or false.

This is how the program stands as of now:

class my_str(str):
        def is_palindrome(self):
                a_string = self.lower()
                length = len(self)
                for i in range(length/2):
                        if a_string[i] != a_string[-(i+1)]:
                                return False
                return True

this = my_str(raw_input("Enter a string: "))
print this.is_palindrome()

Are there any other improvements that I can make to make it more efficient?

Answer 1

It probably isn't a faster implementation but you could use a recursive test. Since you're learning, this construction is very useful in many situation :

def is_palindrome(word): 
    if len(word) < 2:
        return True 
    if word[0] != word[-1]:
        return False 
    return is_palindrome(word[1:-1])

Since this is a rather simple (light) function this construction might not be the fastest because of the overhead of calling the function multiple times, but in other cases where the computation are more intensive it can be a very effective construction.

Just my two cents.

Answer 2

I think the best way to improvise write a palindrome checking function in Python is as follows:

def is_palindrome(s):
   return s == s[::-1]

(Add the lower() call as required.)

Answer 3

Building on Lattyware's answer - by using the Python builtins appropriately, you can avoid doing things like a_string[-(i+1)], which takes a second to understand - and, when writing more complex things than palindromes, is prone to off-by-one errors.

The trick is to tell Python what you mean to do, rather than how to achieve it - so, the most obvious way, per another answer, is to do one of the following:

s == s[::-1]
list(s) == list(reversed(s))
s == ''.join(reversed(s))

Or various other similar things. All of them say: "is the string equal to the string backwards?".

If for some reason you really do need the optimisation that you know you've got a palindrome once you're halfway (you usually shouldn't, but maybe you're dealing with extremely long strings), you can still do better than index arithmetic. You can start with:

halfway = len(s) // 2

(where // forces the result to an integer, even in Py3 or if you've done from __future__ import division). This leads to:

s[:halfway] == ''.join(reversed(s[halfway:]))

This will work for all even-length s, but fail for odd length s because the RHS will be one element longer. But, you don't care about the last character in it, since it is the middle character of the string - which doesn't affect its palindromeness. If you zip the two together, it will stop after the end of the short one - and you can compare a character at a time like in your original loop:

for f,b in zip(s[:half], reversed(s[half:])):
    if f != b: 
        return False
return True

And you don't even need ''.join or list or such. But you can still do better - this kind of loop is so idiomatic that Python has a builtin function called all just to do it for you:

all(f == b for f,b in zip(s[:half], reversed(s[half:])))

Says 'all the characters in the front half of the list are the same as the ones in the back half of the list written backwards'.

Answer 4

While other answers have been given talking about how best to approach the palindrome problem in Python, Let's look at what you are doing.

You are looping through the string by using indices. While this works, it's not very Pythonic. Python for loops are designed to loop over the objects you want, not simply over numbers, as in other languages. This allows you to cut out a layer of indirection and make your code clearer and simpler.

So how can we do this in your case? Well, what you want to do is loop over the characters in one direction, and in the other direction - at the same time. We can do this nicely using the zip() and reversed() builtins. reversed() allows us to get the characters in the reversed direction, while zip() allows us to iterate over two iterators at once.

>>> a_string = "something"
>>> for first, second in zip(a_string, reversed(a_string)):
...     print(first, second)
... 
s g
o n
m i
e h
t t
h e
i m
n o
g s

This is the better way to loop over the characters in both directions at once. Naturally this isn't the most effective way of solving this problem, but it's a good example of how you should approach things differently in Python.

Answer 5

One improvement I can see would be to use xrange instead of range.

Answer 6

What about something way simpler? Why are you creating a class instead of a simple method?

>>> is_palindrome = lambda x: x.lower() == x.lower()[::-1]
>>> is_palindrome("ciao")
False
>>> is_palindrome("otto")
True