implementing a dictionary

Question

Hii ,

I ran across a interview question of implementing a dictionary that can implement the features of auto-completion , auto - correction , spell check etc...

I actually wanted to know which data structure is the best for implementing a dictionary and how one approaches the above required features...

Any links that guide me on this are welcome...

Answer 1

There is just the same answer for this kind of problem: a Trie. Take a look here..

Also suffix trees (or Patricia Trees) can be useful for this purposes..

Answer 2

Tries are a common structure for this. They are a special case of finite-state automata, which have also been used for dictionary construction and spell checking.

Answer 3

You can get auto-completion with any sorted container, for example a set of strings:

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