1

给我一组 N 个单词和一个整数 K。如果前 k 个字母和后 k 个字母完全相同，则 2 个单词属于同一组。如果它们有超过 k 个相同的字母或少于 k 个相同的字母，则这些单词不在同一组中。例如：对于 k=3。

“abcdefg”和“abczefg”在同一个组
“abcddefg”和“abcdzefg”不在同一个组（前k+1个字母相同）
“abc”和“abc”在同一个组

一个词可以在多个组中。例如（k=3）：
“abczefg”和“abcefg”组成一个组
“abczaefg”和“abcefg”组成一个组
“abczaefg”和“abczefg”不在同一个组（前k+1个字母相同)

问题要求我找到包含最大单词数的组数。

我考虑过使用 Trie（或前缀树），我认为这是解决这个问题的正确数据结构，但我不知道如何调整它们来解决这个问题，因为如果 2 个单词有超过 k 个字母的部分相同的不在同一组中使我感到困惑。我的想法的复杂度为 O(N*N*K)，考虑到 N<=10,000 和 K<=100，我认为这个想法不够快。我想向您解释我的想法，但即使对我来说也不清楚，我什至不知道它是否正确，所以我将跳过这一部分。

我的问题是，是否有一种方法可以使用更快的算法来解决这个问题，如果有这样的算法，我请你稍微解释一下。提前谢谢你，如果我没有清楚地解释问题，我很抱歉出现语法错误！

4

1 回答 1

1

首先将共享前 k 个字母和后 k 个字母的所有单词分组。您最大的组必须位于其中一个组中，因为开头和结尾不同的两个单词不可能出现在同一个解决方案中。

因此，在这些组中的每一个中（在它们的开头和结尾共享相同 k 个字母的单词），您需要找到一个最大的单词集，使得没有两个共享第 k+1 个字母，也不共享第 k+1 个'从最后的第一个字母。

构建一个图，其中顶点是从这些组中的一个单词的每一端（重复数据删除）到 (k+1) 的字母对，如果 a，边出现在 (a, b) 和 (c, d) 之间=c 或 b=d。

您需要找到其中没有边的子图。这个简化的问题是“最大独立子图”问题的一个实例，它是 NP 难的，因此您需要通过使用搜索来解决它，并希望给您的单词集不会太讨厌。也许这里的图表可以提供更快的解决方案，但我没有看到。

整个问题的解决方案是上述简化问题之一的最大解决方案。

希望这可以帮助！

于 2012-05-17T14:42:18.510 回答