Gayathri Sampath Gayathri Sampath - 1 month ago 7
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 ?

Answer

Current approach has disadvantage and that most of generated solutions are finally thrown away when checked that solution is/isn't palindrome.

One Idea is that once you pick solution from one side, you can immediate check if there is corresponding solution in last group.

For example lets say that your space is this

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

We can see that if you pick "a" as first pick, there is no "a" in last group and this exclude all possible solutions that would be tried other way.