查找前三個字母相同的段落中的所有單詞？

Question

我們如何以最佳方式解決這個問題？有沒有解決這個問題的算法？例如：我們輸入一些段落並將其作爲輸出，我們得到如下的字母：

a）1.你2.你的3.我們必須找到並打印所有開始3個字母相同的單詞。 4.你自己

二）1.早期2.早期3.最早

這樣我們就得到已經開始共同3個字母」

Answer 1

合理的解決方案，這不是太硬段的所有單詞編碼是爲了維護某種類型的地圖，其中鍵是每個單詞的前三個字母，並且值是以這三個字母開頭的單詞集。您可以掃描段落中的單詞，對於每個遇到的單詞，先剪掉前三個單詞，查找與這些字母對應的地圖條目，然後將該單詞添加到列表中。然後您可以在最後遍歷地圖，找到包含至少兩個單詞的所有集合，然後打印出您找到的每個集羣。總的來說，這種方法的運行時間是O（L），其中L是段落中所有單詞的總長度。要看到這一點，請注意，對於每個單詞，我們會對該單詞的一個固定大小的前綴執行地圖查找，然後將單詞的所有字符複製到地圖中。總的來說，這最多訪問每個角色的次數不變。

Answer 2

Trie帶有前三個字符，然後字索引作爲葉應該做的伎倆。