1

In a technical interview i was asked to implement the t9 dictionary. I knew it can be done using tries, but didn't know how to go about it. Could anyone please explain it ?
Note: Don't mark it as duplicate due to this, as it doesn't contain any explanation.

Community
  • 1
  • 1
Prakhar Agarwal
  • 51
  • 7

1 Answers1

0

1)Build a trie(add all words from dictionary to it).
2)Initially a current node is a root of the trie.
3)When a new character is typed in, you can simply go to the next node from the current node by the edge that corresponds to this character(or report an error if there is nowhere to go).
4)To get all(or k first) possible words with a given prefix, you can just traverse the trie in depth first search order starting from the current node(if you need only k first words, you may stop the search when k words are found).
5)When the entire word is typed in and a new word is started, move to the root again and repeat the steps 3) - 5) for the next word.

P.S All nodes that correspond to a word(not a prefix of a word, but an entire word) can be marked when the trie is build so that it is easy to understand whether a new word is found or not when you traverse the trie during the step 4).

kraskevich
  • 18,368
  • 4
  • 33
  • 45
  • Except that the T-9 dictionary has an ambiguous symbol set ('1'..'9'), not all the letters -- so a given node in the T-9 trie may represent more than one word. The really interesting part is the building of the trie, or, more precisely, the folding of the lower branches of the trie together (to minimise the number of nodes) and the encoding of nodes and node pointers to compress the dictionary -- but that's another story. –  Aug 20 '14 at 09:15