trie的複雜性

Question

如果必須至少讀取輸入字符串數組中的所有字符以逐個將字符串插入到trie中，如何使用trie？所以複雜度是O（size_of_array）。假設輸入的字符串數組是{"hello",world","stack","overflow"}，並且我們想要搜索「stack」，那麼我們將不得不遍歷整個數組，以將鍵插入到trie中。所以複雜度是O（size_of_array）。我們可以做到這一點沒有trie。

Answer 1

特里特點是許多查詢。

• 一個trie提供了一個相對便宜的插入每個字符串。
• 一個trie提供了一個相對便宜的字符串搜索。

這意味着，如果你有一個數組，你需要查詢在一個字符串的存在只是一次 - 它可能不會有很大的幫助，從創建線索的單個查詢是一種浪費。然而，如果你有一本字典，並且你將在數百萬次的時間內查詢它，那麼搜索trie比重新搜索數組效率更高，這就是你從中受益的地方。

Answer 2

嘗試在較不常見的情況下確實有用。但他們有他們的用途。

1. 假設你想實現一個自動完成者，例如，如你在一個文字處理器打字的東西，或引用在命令行的路徑。然後，一個trie對於告訴你什麼是給定前綴的子字符串非常有用。

2. 假設你有一個真正長的字符串的字典，並且你想驗證一個新的很長的字符串是否不在其中。然後，使用散列法，您需要查看新字符串的每個字母。使用一個trie，你可能會很快排除它。