将字符串配对以形成回文串

Question

3

给定N个字符串，每个字符串的长度最多为1000。我们可以通过两个字符串的末尾连接它们。比如，如果一个字符串是“abc”，另一个字符串是“cba”，那么我们可以得到“abccba”和“cbaabc”。有些字符串可能没有与其他字符串连接在一起。同时，任何一个字符串都不能与自己连接。

我们只能将那些形成回文的两个字符串连接起来。因此，我需要告诉您在制作这样的配对之后剩下的最少字符串数量。

例子：假设我们有9个字符串：

aabbaabb 
bbaabbaa
aa
bb
a
bbaa
bba
bab
ab

那么答案就是5。

解释：这里有5个字符串：

"aabbaabb" + "bbaabbaa" = "aabbaabbbbaabbaa"
"aa" + "a = "aaa"
"bba" + "bb" = "bbabb"
"bab" + "ab" = "babab"
"bbaa"

此外，总共可能会有1000个这样的字符串。

- ho_dare ago

2

听起来是个有趣的问题。你到目前为止尝试了什么？ - reto

@reto 我注意到了一些事情。首先，如果一个字符串是回文的，那么我们可以将其他回文添加到它中。如果不是，我们需要这种类型的字符串：{回文} + {剩余字符以使第一个字符串成为回文}。 - ho_dare ago

@reto 主要问题在于假设我们将一些字符串配对，但可能存在更好的配对方案，可以配对剩余的字符串。 - ho_dare ago

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Neithrik · Accepted Answer

1) 创建一个图表，每个单词都有一个节点。

2) 遍历所有单词对，检查它们是否可以拼接成回文。如果可以，就用边连接相应的节点。

3) 现在使用匹配算法来找到最大数量的匹配边：http://en.wikipedia.org/wiki/Blossom_algorithm

时间复杂度：点 1 的复杂度为 O(N)，点 2 的复杂度为 O(n*n*1000)，点 3 的复杂度为 O(V^4)，总复杂度为 O(n^4)。