實施字典

Question

斐伊川，

我整個實施，可以實現自動完成汽車的特徵字典的面試問題跑了 - 修正，拼寫檢查等等......

我其實是想知道哪些數據結構是最適合實施字典和一個如何處理上述要求的功能...

指導我在此歡迎任何鏈接...

Answer 1

只是有這個相同的答案問題的種類：一個Trie。看看here ..

而且後綴樹（或帕特里夏樹）可以爲這個目的有用..

Answer 2

Tries是一個常見的結構。它們是有限狀態自動機的一個特例，它也被用於dictionary construction和spell checking。

Answer 3

你可以自動完成任何排序容器，例如一組字符串：

#include <limits> 
#include <set> 
#include <string> 
#include <vector> 

int main() 
{ 
    std::set<std::string> words = {"foo", "bar", "barber", "baz", "quux"}; 

    std::string starting_with = "ba"; 
    auto lower = words.lower_bound(starting_with); 
    auto upper = words.upper_bound(starting_with + std::numeric_limits<char>::max()); 

    std::vector<std::string> suggested_words(lower, upper); 
}