单词词汇系列

Question

我给出了一组N个单词和一个整数K.如果两个单词具有完全相同的前k个字母和最后k个字母，则它们在同一组中。如果他们有超过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个相同的字母不在同一组中使我感到困惑。我的ideea的复杂度为O（N * N * K），并且考虑到N < = 10,000和K < = 100我认为这个ideea不够快。我想向你解释我的想法，但即使对我来说也不是很清楚，我甚至不知道它是否正确，所以我会跳过这一部分。

我的问题是，如果有一种方法，我可以使用更快的算法解决这个问题，如果有这样的算法，我请你稍微解释一下。非常感谢您的帮助，如果我没有清楚地说明问题，我很抱歉发生了一些严重的错误！

Answer 1

第一组所有共享前k个字母和后k个字母的单词。你最大的群体必须坐在这些群体中的一个群体中，因为没有办法在开始和结束时有两个词在相同的解决方案中有所不同。

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

构造一个图形，其中顶点是从每个末端（去除重复）（k + 1）到其中一个组中的单词的（k + 1）对的字符对，并且边缘出现在（a，b）和（c， d）如果a = c或b = d。

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

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

希望这会有所帮助！