给我一组N个单词和一个整数K。如果两个单词的前k个字母和后k个字母完全相同，则它们在同一组中。如果它们具有多于k个相同的字母或少于k个相同的字母，则这些单词不在同一组中。例如:
对于k ＝ 3。
“abcdefg”和“abczefg”在同一组中
“abcddefg”和“abcdzefg”不在同一组中(前k + 1个字母相同)
“abc”和“abc”在同一组中
一个单词可以超过1组。例如(k = 3):
“abczefg”和“abcefg”组成一个组
“abczaefg”和“abcefg”组成一个组
“abczaefg”和“abczefg”不在同一组中(前k + 1个字母相同)
问题要求我找出包含最大单词数的组数。
我考虑过使用Trie(或前缀树)，并且我认为这是解决此问题的正确数据结构，但我不知道如何适应它们，因为如果2个单词的字母数超过k个完全相同的人不在同一组中。我的想法具有复杂度O(N * N * K)，考虑到N
我的问题是，是否有一种方法可以使用更快的算法来解决此问题，如果有这样的算法，请您稍作解释。预先谢谢您，对于我的语法错误以及如果我没有清楚地解释问题，我深表歉意!
最佳答案
首先对所有共享前k个字母和后k个字母的单词进行分组。您最大的组必须位于这些组中的一个组中，因为在相同的解决方案中，两个在开头和结尾处不同的词是不可能的。
因此，在这些组的每组中(开头和结尾共享相同的k个字母的单词)，您需要找到最大的一组单词，这样就不会有两个共享第k + 1个字母，也没有第k + 1个共享'信末。
构造一个图，其中顶点是从这些组之一中的单词的每一端(去重复)开始的(k + 1)个字母对，并且如果a为a，则边出现在(a，b)和(c，d)之间= c或b = d。
您需要找到一个没有边的子图。这个减少的问题是“最大独立子图”问题的一个实例，该问题是NP难题，因此您需要通过搜索来解决它，并希望给出的单词集不太讨厌。也许这里的图形有些东西可以提供更快的解决方案，但是我看不到。
整个问题的解决方案是上述减少的问题之一的最大解决方案。
希望这可以帮助!