在包含可能子序列列表的列表中查找可能的回文字符串的算法

Question

我有“n”个字符串作为输入，我将这些字符串分成可能的子序列，并将其放入如下列表中

如果输入是：aa，b，aa

我创建一个如下所示的列表（每个列表都包含字符串的子序列）：

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

我想在列表中找到回文的组合。 例如，可能的回文是5-aba，aba，aba，aba，aabaa

这可以通过使用以下代码的暴力算法实现：

^{pr2}$

但是当字符串的数量和长度较大时，这种方法会导致超时。在

有没有更好的方法来解决这个问题？在

Answer 1

当前的方法有缺点，当检查解决方案是/不是回文时，大多数生成的解决方案最终都会被丢弃。在

一个想法是，一旦你们从一边选择了解决方案，你们可以立即检查最后一组中是否有相应的解决方案。在

例如，假设你的空间是这样的

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

我们可以看到，若您选择“a”作为第一个选择，则最后一个组中并没有“a”，这将排除所有可能以其他方式尝试的解决方案。在

Answer 2

第二个版本

此版本使用一个名为seen的集合，以避免多次测试组合。在

请注意，您的函数isPalindrome()可以简化为单个表达式，所以我删除了它，只进行了内联测试，以避免不必要的函数调用的开销。在

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))

Answer 3

对于较大的输入，您可能会从第一个数组中抓取单词，并将它们与最后一个数组的单词进行比较，以检查这些对是否仍然允许形成回文，或者这样的组合永远不会通过从剩余的单词中插入数组来产生回文。在

通过这种方法，您可能会取消很多可能性，而且一旦您确定一对仍在运行，这种方法可以递归地重复。然后保存两个单词的公共部分（当然，当第二个单词颠倒时），并将其余字母分开，以便在递归部分使用。在

根据这两个单词中哪一个较长，您可以将剩余的字母与从左到右下一个数组中的单词进行比较。在

这会给搜索树带来很多早期修剪。所以笛卡尔积的组合就不能完成。在

我还编写了从给定单词中获取所有子字符串的函数，您可能已经有了：

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 > 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 > 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)

我和martineau发布的解决方案做了时间对比。对于我使用的示例数据，此解决方案大约快100倍：

看到它运行在repl.it

另一个优化

当第一个数组有多个具有相同字符串的条目时，不重复搜索也可以获得一些好处，比如示例数据中的'a'。包含第二个'a'的结果显然与第一个相同。我没有编码这种优化，但它可能是一个想法，以提高性能甚至更多。在