Gayathri Sampath - 1 year ago 58
Python Question

# Algorithm for finding the possible palindromic strings in a list containing a list of possible subsequences

I have "n" number of strings as input, which i separate into possible subsequences into a list like below

If the Input is : aa, b, aa

I create a list like the below(each list having the subsequences of the string):

``````aList = [['a', 'a', 'aa'], ['b'], ['a', 'a', 'aa']]
``````

I would like to find the combinations of palindromes across the lists in aList.
For eg, the possible palindromes for this would be 5 - aba, aba, aba, aba, aabaa

This could be achieved by brute force algorithm using the below code:

``````d = []
def isPalindrome(x):
if x == x[::-1]: return True
else: return False
for I in itertools.product(*aList):
a = (''.join(I))
if isPalindrome(a):
if a not in d:
d.append(a)
count += 1
``````

But this approach is resulting in a timeout when the number of strings and the length of the string are bigger.

Is there a better approach to the problem ?

``````[["a","b","c"], ... , ["b","c","d"]]