7
\$\begingroup\$

I was solving a question where I had to find all possible unique palindromes of size greater than 1 for a string.

I was able to come up with the solution shown below. If I am not mistaken it is an \$O(n^2)\$ solution. I'd like feedback on improving the code and if my understanding of its time complexity is correct.

def check_palin(word):
    for i in xrange(len(word)/2):
        if word[i] != word[-1*(i+1)]:
            return False
    return True

def all_palindromes(string):

    left,right=0,len(string)
    j=right
    results=[]

    while left < right-1:
        temp = string[left:j] #Time complexity O(k)
        j-=1

        if check_palin(temp):
            results.append(temp)

        if j<left+2:
            left+=1
            j=right

    return list(set(results))

print all_palindromes("racecarenterelephantmalayalam")

Output:

['aceca', 'layal', 'cec', 'alayala', 'racecar', 'ele', 'ere', 'aya', 'malayalam', 'ala']
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Do please allow for others to answer your question, and not be to eager accepting answers to soon. \$\endgroup\$
    – holroy
    Nov 10, 2015 at 20:13
  • \$\begingroup\$ I tried running your code, but it kept giving me the error message:" TypeError: 'float' object cannot be interpreted as an integer" even when I tried with the same input as you did. Why is this a case?? \$\endgroup\$
    – user177196
    Aug 28, 2017 at 19:03

2 Answers 2

7
\$\begingroup\$

All in all your code reads rather nicely, and there are just minor adjustments regarding style. After those comments, I'd also like to take the opportunity to propose a better algorithm for finding these palindromes.

  • Add space around expressions – When assinging to left and right you do it on one line, which is neat, butpleaseaddspaces to increase readability. It is much better as left, right = 0, len(string). Similar use j -= 1, and if j < left + 2:
  • Avoid shortening names – Although check_palin saved you a few characters, please don't shorten the names. And unless within a tight loop, avoid single letter variable names, like j
  • Use a set directly, instead of list – You could initialize with results = set(), and use results.add(temp) to do all your work directly on a set instead of a list. And the return would then be return list(set)
  • Consider using generators – Given a really long text, you would need to hold all palindromes in memory, using generators you could eliminate that memory issue, but you might return palindromes you've returned before (i.e. 'ala' which appears twice)
  • Add docstrings to your functions – Adding docstrings helps you remember what the function actually does, and also helps you to clarify what this method actually does or what it returns. If you don't have a clear vision of what to write in a docstring, you most likely don't really have a clear vision of what the function does either...

Another algorithm

Your algorithm builds up all permutations of substrings in the given text, and checks each and every one of these are palindromes. This gives a lot of extraneous checks as you keep on checking not taking advantage of known information. One option to get better response could be to check if the current word you're checking is already part of the results set, alongside with if you find a palindrome, then split it down into all the sub palindromes.

Another option is to switch the algorithm around, and make the loop go through each character in the text, and see if you've got a palindrome when extending with the left and right character of your current character. This way you'll stop checking when it's not a palindrome and don't waste time checking non-palindromes.

Here is that algorithm in working code:

DEFAULT_TEXT = "racecarenterelephantmalayalam"

def all_palindromes(text=DEFAULT_TEXT):
    """Return list with all palindrome strings within text.

    The base of this algorithm is to start with a given character,
    and then see if the surrounding characters are equal. If they
    are equal then it's a palindrome and is added to results set,
    extend to check if the next character on either side is equal, 
    adding to set if equal, and breaking out of loop if not.

    This needs to be repeated twice, once for palindromes of 
    odd lengths, and once for palindromes of an even length."""

    results = set()
    text_length = len(text)
    for idx, char in enumerate(text):

        # Check for longest odd palindrome(s)
        start, end = idx - 1, idx + 1
        while start >= 0 and end < text_length and text[start] == text[end]:
            results.add(text[start:end+1])
            start -= 1
            end += 1

        # Check for longest even palindrome(s)
        start, end = idx, idx + 1
        while start >= 0 and end < text_length and text[start] == text[end]:
            results.add(text[start:end+1])
            start -= 1
            end += 1

    return list(results)


def main(text=DEFAULT_TEXT):
    print all_palindromes(text)

I runned your version, and mine version multiple times with a few various texts. With the default text you supplied your version used 440 µs, whilst mine used 27 µs (7 % of your time). When tripling the length of the text, yours used approx 4 000 µs, whilst mine used 77 µs (2 %). Tripling the triplet, your used 15.7 ms, and mine used 151 µs (<1 %).

As can be seen, your version is growing faster as you always check everything, whilst my version depends on actual number of palindromes in correlation to length of text. Somewhat imprecise one can say that your algorithm has a constant time complexity \$O(n^2)\$, whilst mine has \$O(n*m)\$ where \$n\$ is length of text, whilst \$m\$ is number of palindromes. As number of palindromes is usually quite a bit lower than length of text, my version tends to go towards \$O(n)\$, whilst your version remain constantly at \$O(n^2)\$.

\$\endgroup\$
11
  • \$\begingroup\$ Thank you for the amazing explanation and tips. This was extremely helpful! \$\endgroup\$
    – aamir23
    Nov 10, 2015 at 23:22
  • \$\begingroup\$ @aamir23, No problem! :) \$\endgroup\$
    – holroy
    Nov 10, 2015 at 23:23
  • \$\begingroup\$ Is your method based of Manacher's algorithm of finding the longest palindrome substring? \$\endgroup\$
    – aamir23
    Nov 10, 2015 at 23:29
  • \$\begingroup\$ Nope... Just intuition and experience... That does not say that it isn't actually a replica of Manacher's algorithm... I don't that algorithm, though \$\endgroup\$
    – holroy
    Nov 10, 2015 at 23:30
  • \$\begingroup\$ @aamir23, That was kind of fun. It is indeed a variant over Manacher's algorithm. Didn't know that, as I just implemented something which was intuitive to me, and which seemed easier and faster! \$\endgroup\$
    – holroy
    Nov 10, 2015 at 23:32
7
\$\begingroup\$

Time complexity

Yes, your solution has a O(n^2) time complexity. As the output is n^2 where the input is n, achieving a better time complexity is impossible.

Look at the following code + output:

for i in range(1, 51):
    string = "a" * i
    permutations = list(palindrome_substrings("a"*i))
    print(len(string), len(permutations), len(permutations) /  float(len(string)))

(1, 1, 1.0)
(2, 3, 1.5)
(3, 6, 2.0)
(4, 10, 2.5)
(5, 15, 3.0)
(6, 21, 3.5)
(7, 28, 4.0)
(8, 36, 4.5)
(9, 45, 5.0)
(10, 55, 5.5)
(11, 66, 6.0)
(12, 78, 6.5)
(13, 91, 7.0)
(14, 105, 7.5)
(15, 120, 8.0)
(16, 136, 8.5)
(17, 153, 9.0)
(18, 171, 9.5)
(19, 190, 10.0)
(20, 210, 10.5)
(21, 231, 11.0)
(22, 253, 11.5)
(23, 276, 12.0)
(24, 300, 12.5)
(25, 325, 13.0)
(26, 351, 13.5)
(27, 378, 14.0)
(28, 406, 14.5)
(29, 435, 15.0)
(30, 465, 15.5)
(31, 496, 16.0)
(32, 528, 16.5)
(33, 561, 17.0)
(34, 595, 17.5)
(35, 630, 18.0)
(36, 666, 18.5)
(37, 703, 19.0)
(38, 741, 19.5)
(39, 780, 20.0)
(40, 820, 20.5)
(41, 861, 21.0)
(42, 903, 21.5)
(43, 946, 22.0)
(44, 990, 22.5)
(45, 1035, 23.0)
(46, 1081, 23.5)
(47, 1128, 24.0)
(48, 1176, 24.5)
(49, 1225, 25.0)
(50, 1275, 25.5)

As you can see, not only the output size grows with the input, the ratio between output size and input size grows too. This means that the time complexity is quadratic.

Generators and all

As far as the code is concerned, it is not Pythonic, it looks like C as it does not make use of generator expressions and built-ins like any or all.

def is_palindrome(word):
    return all(word[i] == word[-1*(i+1)] for i in xrange(len(word)//2))

I kept your way of looping and multiplying by -1, but now the code reads at a higher level: all the i-th chars must equal the (-1 * (i+1)) - th chars. And the efficiency is the same as all short-circuites (aborts the computation as soon as it finds a counterexample.)

Separation of concerns

Getting the substrings of a string is interesting in its own right.Why am I forced to get only the palindrome ones? Make substrings a separate function.

Going one level deeper

You can actually nest the loops in the generator expression, getting the substrings of a string may be written as:

def substrings(string):
    return (string[i:j+1] for i in range(len(string)) for j in range(i, len(string)))

Or in a more imperative-looking (but equivalent) manner:

def substrings(string):
    for i in range(len(string)):
        for j in range(i, len(string))):
            yield string[i:j+1]

The final function

And getting the palindrome substrings is now very easy:

def palindrome_substrings(string):
    return (i for i in substrings(string) if is_palindrome(i))

Side note about names

Use long descriptive names, over cryptic abbreviations:

  • check_palin -> check_palindrome or following the is_ convention (boolean-returning functions should have a name starting with is_) is_palindrome

  • all_palindromes: What does all stand for? It stands for substrings so just write it like that: -> palindrome_substrings

Bug fix

a is a palindrome, in general all single char strings are palindromes, so your code not returning them means it has a bug. My code rightly returns single char palindromes.

\$\endgroup\$
5
  • \$\begingroup\$ Thank you for the detailed explanation and tips. And you're correct that it should return single char strings, I forgot to mention that I was looking only for palindromes with length > 1. \$\endgroup\$
    – aamir23
    Nov 9, 2015 at 2:50
  • 1
    \$\begingroup\$ And I think there is a more efficient way to handle this (than generating all possible strings and checking if every single one is a palindrome). The worst case will still be O(n^2), but the average might be much better [I need some time to create it] \$\endgroup\$
    – oliverpool
    Nov 9, 2015 at 11:05
  • 1
    \$\begingroup\$ @oliverpool You could check out the accepted answer posted by holroy. \$\endgroup\$
    – aamir23
    Nov 10, 2015 at 23:28
  • \$\begingroup\$ I had kind of the same ground idea (go through the original string once), but my implementation was more compllicated as the one of @holroy \$\endgroup\$
    – oliverpool
    Nov 11, 2015 at 7:56
  • \$\begingroup\$ @aamir23 Good, but worst-case is still n^2 in the case all substings are palindromes \$\endgroup\$
    – Caridorc
    Nov 11, 2015 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.