創建詞典樹的複雜性是什麼

Question

創建詞典樹的複雜性是什麼？

Answer 1

適當的數據結構可能是一個排序列表。在這種情況下，這變成了二分搜索問題，所以O（log n）。

Answer 2

只是運行一個簡單的循環，並檢查每個單詞是否以任何開頭。

幾乎在每種語言中都有一個構建函數用於檢查一個字符串是否以另一個字符串開頭。

複雜度是O（log n），而n是詞典中單詞的數量。

Answer 3

如果您在輸入中創建了prefix tree，則可以在恆定時間內執行此查詢。

編輯

該查詢是在搜索字符串的長度是線性的。我的意思是說，關於單詞列表的大小是不變的。

Answer 4

正如上面提到的Gabe Trie是一個很好的解決方案，但對於有大量單詞的字典實現起來有點困難。如果O（n log n）算法適合你，你可以用二分查找來解決這個問題。這裏是用C編寫的代碼：

 
char dict[n][m]; // where n is number of words in dictionary and 
       // m is maximum possible length of word 
char word[m]; // it's your word 

int l = -1, r = n; 
while(l+1 < r) { 
    int k = (l+r)/2; 
    if(strcmp(dict[k], word) < 0) l = k; 
    else r = k; 
} 

int len = strlen(word); 
l++; // first word's index with greater or equal prefix then word is l+1 
bool matches = (strlen(word[l]) >= len); 
for(int i = 0; i < len && matches; i++) { 
    if(word[i] != dict[l][i]) { 
    matches = 0; 
    } 
} 

if(matches) { 
    printf("given word is prefix of %dth word.", l); 
} else { 
    printf("given word isn't in dictinary."); 
}