实现字典

Question

嗨，

我遇到了一个面试问题，关于实现一个字典，它可以实现自动完成，自动更正，拼写检查等功能...

我实际上想知道哪种数据结构最适合实现字典以及如何实现接近上述所需的功能...

欢迎任何指导我的链接...

Answer 1

对于此类问题，有相同的答案：Trie。看看这里..

还有后缀树（或帕特里夏树）可以用于此目的..

Answer 2

Tries 是一种常见的结构。它们是有限状态自动机的特例，也用于 字典构建和拼写检查。

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);
}