查找數量的字典

Question

以下是在一次採訪中向我詢問的問題。 我們知道食物的一種是：茶和吃 現在的問題是： 我們有一個程序。我們向該計劃提供一萬個字母的列表。 我們運行該程序。 現在在運行時，我們爲這個程序提供一個詞，例如。 「eat」 現在程序應該返回一萬個字母列表中存在的anagrams的數量。因此，對於「吃」的輸入，它應該返回2.

什麼將是存儲那些10000個字母，以便找到字謎的數量變得容易策略。

Answer 1

令每個單詞的字母，以減少它的排序規則，即tea變得aet。

然後，只需把這些單詞中的一個（哈希）地圖計數（包括tea和ate映射到aet，所以我們會在地圖上有(aet, 2)）

然後，當你得到一個字，重新排序如上所述的字母，並對count進行查找。

運行時間：

假設n詞語的列表，以及m的平均字長...

預計O(nm log m)預處理，預計O(m log m)每次查詢。

這是m log m上，我們只是做一個簡單的排序一個單詞的字母的假設。

每個查詢所花費的時間預計將在列表中的字的數量的影響（即，哈希映射就給預期O(1)查找時間）。