Palindromic sub-sequences in python
This bit of code returns all palindromic subsequences in the input string. If the line marked #In-efficient
is better implemented (I am lazy), the running time is O(n<sup>2</sup>)
. Can you find a better solution?
#!/usr/bin/env python
def get_palindromes(str):
""" Return all palindromes in str of minimum size 3 """
length = len(str) + 1
found = []
for i in xrange(0, length):
for j in xrange(i+3, length):
mid = i + ((j - i) / 2)
if str[i:mid] == str[mid+1:j][::-1]: # In-efficient
found.append(str[i:j])
return found
if __name__ == '__main__':
print get_palindromes('efeababaf')