Gayathri Sampath - 7 months ago 27

Python Question

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

For eg, the possible palindromes for this would be 5 - aba, aba, aba, aba, aabaa

This could be achieved by

`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.