Algorithm for finding the possible palindromic strings in a list containing a list of possible subsequences
<p>I have "n" number of strings as input, which i separate into possible subsequences into a list like below</p>

<p>If the Input is : aa, b, aa</p>

<p>I create a list like the below(<strong>each list having the subsequences of the string</strong>):</p>

<pre><code>aList = [['a', 'a', 'aa'], ['b'], ['a', 'a', 'aa']]
</code></pre>

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

<p>This could be achieved by <em>brute force algorithm</em> using the below code:</p>

<pre><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
</code></pre>

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

<p>Is there a better approach to the problem ?</p>

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

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

<p>For example lets say that your space is this</p>

<pre><code>[["a","b","c"], ... , ["b","c","d"]]
</code></pre>

<p>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.</p>

python algorithm