4

How can we implement A dictionary that is used in mobile (which is used when we type A message on mobile phone)? It shows the list of words that can be formed with entered characters.

Example:

4663 can be good, gone, home.

467 it shows suggested word as important.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
RATHI
  • 5,129
  • 8
  • 39
  • 48

1 Answers1

3

A simple solution would be to pre - compute the words and build a trie tree having digits in the nodes and each leaf node would have a link to a linked list /array(or some other data structure) of strings that can be formed using those digits.

At any given point , for example the user has typed 4663 -> go to all children of the last node(having the digit 3 in the example) that are not null, reach the leaf nodes through the various paths and print the valid words.

Note : Since the number of digits=10 only , the size of the trie tree would be limited. A ternary search tree(TST) could also be used in place of the trie tree but here , but since there are only 10 digits , there would not be much significant advantages of using a TST I guess.

EDIT - As pointed out by user1168577 , using a heuristic like frequency of usage, words can be shown in that order.

Rndm
  • 6,710
  • 7
  • 39
  • 58
  • It is a bad solution. trie only gives you **all words that starts with the given prefix** - there could be thousands of them - how will you chose the best match and suggest them? I think this is what the OP is after. – amit Jul 14 '12 at 09:02
  • 4
    @amit - I disagree. Trie is a good start. Once you get a prefix, any dictionary word starting with that prefix is eligible to be shown. Based on some heuristics i.e. frequency of usage the words can be shown. – user1168577 Jul 14 '12 at 09:10
  • @user1168577 : Yes, the heuristic you mentioned would be a good one in this case. – Rndm Jul 14 '12 at 09:12