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>For larger input you could probably get some time gain by grabbing words from the first array, and compare them with the words of the last array to check that these pairs still allow for a palindrome to be formed, or that such a combination can never lead to one by inserting arrays from the remaining words in between. </p>

<p>This way you probably cancel out a lot of possibilities, and this method can be repeated recursively, once you have decided that a pair is still in the running. You would then save the common part of the two words (when the second word is reversed of course), and keep the remaining letters separate for use in the recursive part. </p>

<p>Depending on which of the two words was longer, you would compare the remaining letters with words from the array that is next from the left or from the right.</p>

<p>This should bring a lot of early pruning in the search tree. You would thus not perform the full Cartesian product of combinations.</p>

<p>I have also written the function to get all substrings from a given word, which you probably already had:</p>

<pre><code>def allsubstr(str):
    return [str[i:j+1] for i in range(len(str)) for j in range(i, len(str))]

def getpalindromes_trincot(aList):

    def collectLeft(common, needle, i, j):
        if i &gt; j:
            return [common + needle + common[::-1]] if needle == needle[::-1] else []
        results = []
        for seq in aRevList[j]:
            if seq.startswith(needle):
                results += collectRight(common+needle, seq[len(needle):], i, j-1)
            elif needle.startswith(seq):
                results += collectLeft(common+seq, needle[len(seq):], i, j-1)
        return results

    def collectRight(common, needle, i, j):
        if i &gt; j:
            return [common + needle + common[::-1]] if needle == needle[::-1] else []
        results = []
        for seq in aList[i]:
            if seq.startswith(needle):
                results += collectLeft(common+needle, seq[len(needle):], i+1, j)
            elif needle.startswith(seq):
                results += collectRight(common+seq, needle[len(seq):], i+1, j)
        return results

    aRevList = [[seq[::-1] for seq in seqs] for seqs in aList]
    return collectRight('', '', 0, len(aList)-1)

# sample input and call:
input = ['already', 'days', 'every', 'year', 'later'];
aList = [allsubstr(word) for word in input]
result = getpalindromes_trincot(aList)
</code></pre>

<p>I did a timing comparison with the solution that martineau posted. For the sample data I have used, this solution is about 100 times faster:</p>

<p>See it run on <a href="https://repl.it/Dx2V/1" rel="nofollow">repl.it</a></p>

<h3>Another Optimisation</h3>

<p>Some gain could also be found in not repeating the search when the first array has several entries with the same string, like the <code>'a'</code> in your example data. The results that include the second <code>'a'</code> will obviously be the same as for the first. I did not code this optimisation, but it might be an idea to improve the performance even more.</p>

python algorithm