<p>对于较大的输入,您可能会从第一个数组中抓取单词,并将它们与最后一个数组的单词进行比较,以检查这些对是否仍然允许形成回文,或者这样的组合永远不会通过从剩余的单词中插入数组来产生回文。在</p>
<p>通过这种方法,您可能会取消很多可能性,而且一旦您确定一对仍在运行,这种方法可以递归地重复。然后保存两个单词的公共部分(当然,当第二个单词颠倒时),并将其余字母分开,以便在递归部分使用。在</p>
<p>根据这两个单词中哪一个较长,您可以将剩余的字母与从左到右下一个数组中的单词进行比较。在</p>
<p>这会给搜索树带来很多早期修剪。所以笛卡尔积的组合就不能完成。在</p>
<p>我还编写了从给定单词中获取所有子字符串的函数,您可能已经有了:</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 > 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)
</code></pre>
<p>我和martineau发布的解决方案做了时间对比。对于我使用的示例数据,此解决方案大约快100倍:</p>
<p>看到它运行在<a href="https://repl.it/Dx2V/1" rel="nofollow">repl.it</a></p>
<h3>另一个优化</h3>
<p>当第一个数组有多个具有相同字符串的条目时,不重复搜索也可以获得一些好处,比如示例数据中的<code>'a'</code>。包含第二个<code>'a'</code>的结果显然与第一个相同。我没有编码这种优化,但它可能是一个想法,以提高性能甚至更多。在</p>