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>

<h1>Second version</h1>

<p>This version uses a set called <code>seen</code>, to avoid testing combinations more than once.</p>

<p>Note that your function <code>isPalindrome()</code> can simplified to single expression, so I removed it and just did the test in-line to avoid the overhead of an unnecessary function call.</p>

<pre><code>import itertools

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

d = []
seen = set()
for I in itertools.product(*aList):
    if I not in seen:
        seen.add(I)
        a = ''.join(I)
        if a == a[::-1]:
            d.append(a)

print('d: {}'.format(d))
</code></pre>

python algorithm