How to generate a list of palindrome numbers within a given range?

Question

Let's say the range is : 1 ≤ X ≤ 120

This is what I have tried:

>>> def isPalindrome(s):
    ''' check if a number is a Palindrome '''
    s = str(s)
    return s == s[::-1]

>>> def generate_palindrome(minx,maxx):
    ''' return a list of Palindrome number in a given range '''
    tmpList = []
    for i in range(minx,maxx+1):
        if isPalindrome(i):
            tmpList.append(i)

    return tmpList

>>> generate_palindrome(1,120)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111]

However, this is O(n).

How do I improve this algorithm to make it faster ?

PS. This is Python 2.7

Answer 1

Your method could be:

palindromes = [x for x in xrange(min, max) if isPalindrome(x)]

The only way you can do this and have a non-linear algorithm is to generate the palindromes yourself, instead of testing.

A palindrome can be generated by taking a previous palindrome, and adding the same number to the left and right side, so that is a starting point.

Let's say you start at 1:

Possible palindromes are obtained by adding each digit from 1:9 to the left and right:

111
212
313
...

And also, you have to generate the several entries where every digit is equal in the range...