單詞詞彙系列

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難題，因此您需要通過搜索來解決它，並希望您給出的一組單詞不是太討厭。也許這裏有一些圖表提供了一個更快的解決方案，但我沒有看到它。

整個問題的解決方案是上述減少問題之一的最大解決方案。

希望這會有所幫助！