Trie數據結構

Question

給定N個字符串。每個字符串只包含來自a−j（含）的小寫字母。如果沒有字符串是另一個字符串的前綴，則稱該組N字符串爲GOOD SET。否則，它是BAD SET。

例如，aab，abcde，aabcd是BAD SET因爲aab是aabcd前綴。

打印GOOD SET如果它滿足問題要求。 否則，打印壞設置和條件失敗的第一個字符串。

輸入格式：
第一行包含N，即集合中的字符串數。 然後接下來N行，其中第i行包含第i個字符串。

限制條件：
1≤N≤105 1≤長度字符串的≤60

輸出格式：
輸出GOOD SET如果設定是有效的。
否則，輸出壞設置後跟條件失敗的第一個字符串。

任何人都可以對此建議嗎？

Answer 1

構造一個trie，將每個字符串逐個插入到trie中，記錄指向表示插入到trie中的每個字符串的節點的指針。完成後，掃描所有字符串的節點指針。如果任何這些結束在內部節點，那麼它是一個壞的設置。否則，（所有字符串在不同的葉子上結束），它是一個好設置。時間和空間複雜度與所有字符串的總長度都是線性的。