CareerCup

Dictionary using trie - each node as number bit, so there will be a node 2 representing "abc", Hence tree till have 9 nodes as root and so on.

construct dictionary using trie with augmentation.
Instead of char key's, use numbers corresponding to combination for chars.

for eg. 2 for {a,b,c} 
	     3 for {d,e,f} and so on till 9 {w,x,y,z}

so the first level would contain 9 nodes.
Consider a word "book" in dict.
It would be inserted in order - 2665.
create a linked list / priority queue of words corresponding to same number combination in the terminal node and display the words either randomly or based upon priority.

277451366514612382623

4056830968

6259

class Key
{
public:
    Key()
    {
    }
    static int zero,two,three;
    static int four,five,six,seven,eight,nine;
    static int get( char ch )
    {
        if ( ( ch == 'a' ) || ( ch == 'b' ) || ( ch == 'c' ) )
        {
            return Key::two;
        }
        if ( ( ch == 'd' )  || ( ch == 'e' )  || ( ch == 'f' ) )
        {
            return Key::three;
        }
        if ( ( ch == 'g' )  || ( ch == 'h' )  || ( ch == 'i' ) )
        {
            return Key::four;
        }
        if ( ( ch == 'j' )  || ( ch == 'k' )  || ( ch == 'l' ) )
        {
            return Key::five;
        }
        if ( ( ch == 'm' )  || ( ch == 'n' )  || ( ch == 'o' ) )
        {
            
            return Key::six;
    }
    if ( ( ch == 'p' )  || ( ch == 'q' )  || ( ch == 'r' )  || (ch == 's'))
    {
        return Key::seven;
    }
    if ( ( ch == 't' )  || ( ch == 'u' )  || ( ch == 'v' ) )
    {
        return Key::eight;
    }
    if ( ( ch == 'w' )  || ( ch == 'x' )  || ( ch == 'y' )  || (ch == 'z'))
    {
        return Key::nine;
    }
    return Key::zero;
}
};
int Key::zero = 0;
int Key::two = 2;
int Key::three = 3;
int Key::four = 4;
int Key::five = 5;
int Key::six = 6;
int Key::seven = 7;
int Key::eight = 8;
int Key::nine = 9;

class T9dict
{
    vector<unordered_set<string>> _dict;
public:
    T9dict( vector<string>& words )
    {
        _dict.resize(10);
        addWords(words);
    }
    void addWords( vector<string>& words  )
    {
        for (string w: words)
        {
            if ( w.empty() )
                continue;
            
            _dict[Key::get(w[0])].insert(w);
        }
    }
    const unordered_set<string>& lookup( int key )
    {
        return _dict[Key::get(key)];
    }
};

include std

i think the best answer would be using hash tables.. as you all know hash uses 0(1) as the complexity.Storing the known words in hash table and when the user wants to add a user defined words to dictionary we can just add it to the hash.this way its simpler and faster implementation of t9 dictionary.