檢查字是否可以由給定的字母快速製成

我有一些字母和頻率計數。我有很長的單詞列表（1M表示）。檢查字是否可以由給定的字母快速製成

假設我有A-1, B-1, D-1（「最多一個A，最多一個B，最多一個D」），那麼我可以讓"BAD"，但不"RAD"

我能知道在哪個詞可以做出來的這些字母，對數時間，或類似的東西，而不是遍歷所有的單詞，並看看字中的每個字母的計數？

什麼數據結構可以用於這些單詞？一個特里可能？我不知道他們。如果我可以用它存儲每個單詞所需的字母，那也是非常好的。請幫忙！

來源

2013-02-10 Bruce

對數是什麼？你將不得不檢查每一個單詞，所以顯然你不會發現任何在單詞數量上是次線性的算法。 – ruakh 2013-02-10 03:16:43

@ruakh這取決於。如果您只需設置一次單詞列表，但會嘗試多次，您可以通過預處理快速查找單詞。 – Patashu 2013-02-10 03:18:44

儘管如此，我給了你每封信100個字，並要求你找到所有可以從這些字中創建的單詞。在這種情況下，你必須寫出所有的單詞。 – nneonneo 2013-02-10 03:21:41

下面是一個數據結構的（文字）草圖。

   [root] 
     ----- | ----- 
     A1  A2  B1 ... 
    ----/- ---|--- -\---- 
B1 C1 [a] B1 B2 C1 C1 C2 D2 ...

這是一棵樹，其中葉節點是單詞列表中的單詞。葉子節點上的單詞完全由一系列由從根節點到該節點的路徑組成的字母組成。非葉節點標有字母和數字。節點的孩子必須是葉子（一個單詞），或者在字母表後面嚴格限定一個字母。所以，要去「貓」，你沿着路徑A1,C1,T1，和cat（和act）將是T1的孩子。在每個節點上，您遍歷計數≤您輸入計數的子項（因此對於包A3, C1, T2，您將遍歷標記爲A1，A2，A3，C1，T1或T2的任何節點）。

遍歷在最壞的情況下（每個單詞匹配）需要O（n）時間，但平均需要的時間要少得多。對於一個小的輸入包，它只會遍歷幾個節點。對於一個大的輸入包，它遍歷許多節點，但它也會找到很多單詞。

該樹包含最多單詞表中每個字母的一個節點，因此它的大小最多與單詞表的長度成正比。

這是一個時間和節省空間的結構，它可以計算和比較容易儲存 - 它不會採取更多的空間比你的單詞表，並查詢非常快。

來源

2013-02-10 03:47:20 nneonneo

這是一個很好的解決方案，你只需要正確數量的字母（因爲它是我的），但是由於你必須在_many_不同的位置存儲'cat'（因爲它可以從'act'到' aaaaaccccccccccttttxyzzy'）。這是我在評論中提到的空間成本。 – paxdiablo 2013-02-10 05:31:04

不，您只能將它存儲在一個位置：作爲A1-C1-T1（未壓縮版本中的A1-B0-C1-D0 -...- S0-T1）的孩子。如果給出'aaaaacccccccccctxyzzy'作爲輸入，則將作爲算法的一部分遍歷'A1-C1-T1'（以及'A1-C2-T1'「acct」，'X1-Y2-Z2'「xyzzy」等）。（這裏的符號假定正在使用零壓縮，即X1'是根的直接子節點）。 – nneonneo 2013-02-10 05:32:10

好的，那麼效率就不如你了。是的，這取決於單詞表中字符的數量，但爲了找到單詞，必須爲每個字母組合遍歷一次該樹。例如，'act'將需要對'a'，'c'，'t'，'ac'，'ca'，'at'，'ta'，'ct'，'tc'和這六個不同的組合'act'。這對大袋子尺寸來說會不起作用。 – paxdiablo 2013-02-10 05:38:54

如果你需要有所有字母的話，我已經做了類似的東西之前（我的填字遊戲作弊程序，我很慚愧地說）。

我把字典文件和預處理它使每一行有字母排序，後跟字本身，如：

aaadkrrv:aardvark

然後，如果你有字母ardvkraa，那種，然後尋找在冒號前包含該字符串的行。我使用了grep，因爲O（n）足夠好，但是您可以輕鬆地將所有行放入平衡二叉樹中，以便爲您提供O（log n）複雜性。

如果您只是在使用字母后僅使用的某些，但沒有明確說明這是否是您想要的內容，這將毫無幫助。

來源

2013-02-10 03:23:27 paxdiablo

是的，只能使用部分字母的單詞是可能的。 – Bruce 2013-02-10 03:32:10

在Python中，'d = {''.join（sorted（w））：w for w in wordlist};打印d [''。join（sorted（s））]'將在O（n）預處理時間和O（1）查找時間中執行，不需要二叉樹。（但這並不能解決OP的問題）。 – nneonneo 2013-02-10 03:33:44

@Bruce，那麼我認爲你可能只限於O（n）。爲時間交易空間總是可能的，但我懷疑這裏的空間成本太高了。 – paxdiablo 2013-02-10 03:37:48

我不能說我能把握的問題，你從你的描述呈現100％，但是從我所看到的，你可以做到以下幾點：

你索引你的單詞列表。例如，'B1'是一個索引，它將包含一個包含不多於一個字母B的條目列表，或者滿足您正在解決的問題的要求。您也可以擁有「複合」索引，例如「A1B1」。鑑於您可以負擔索引的時間預算，您可以創建相當深的哈希值。如果您使用的是帶有26個字母的字母表，並且想要散列4個字母的組合，則只有14,950個索引，如果是3個字母，則只有2,600個字母。索引可以在列表的一次迭代期間構建，因此它們的創建是線性的。一旦你經歷了這個階段，你的大部分查找將是對數的。在我的例子中，你的4個字母單詞查找將是一個單一的提取。當然，對於較長的字母組合，首先使用索引，然後迭代。

來源

2013-02-10 04:01:15 BuddhaGautama

檢查字是否可以由給定的字母快速製成

回答

相關問題