CODEWITHSUNDEEP
javadata-structuresdictionary
Harish
Harish

Reputation: 3483

Buiding a dictionary using java

I am writing a dictionary kind of application in java.I have a list of 2.5 million words lookup list in a word document.My dictionary is based on a mobile application.So when the user types 4 I should get words starting with letter namely ghi and for if i type 2 I should take letters starting with ghi and second letter is one of abc.

Now what should be the approach to be followed. 1. What should be the datastructure to store the list of words based on space and time complexity?

2.I am confused because if I type 15 digits its almost mindboggling combination to do a brute force check after all the digits are typed.So I should take words starting with ,contains these.

Can anyone guide me?

Upvotes: 0

Views: 480

Answers (3)

GolezTrol
GolezTrol

Reputation: 116100

Just thinking, maybe you could build a tree of numbers. Each number represents 3 letters as you said. Each node of the tree represents a single character in the tree, so to store the word 'cow', your tree will look like this:

   [1(abc) , 2 , 3 , 4 , 5 , 6 ...]
   /\
  [... 4 , 5 , 6 (mno) , 7 ... ]
               /\
        [... 7 , 8 , 9(wxyz) ]

Under that last node, you'll put the word cow, and any other words that can be made of the same series of letters (like 'any', 'bow', 'box'). Then, when a user types '169', you can present all the tree-letter words that are found in that node, followed by longer words that are found by following sub-nodes under the selected node.

Upvotes: 0

Stan Kurilin
Stan Kurilin

Reputation: 15792

I thinks you should build structure thats will map each world into numbers which it can be presented. and build map from such mapping. So you need List<Integer> and Multiset (Map<Integer, Set<String>>) and function for mapping.

Upvotes: 0

NPE
NPE

Reputation: 500157

Well, first of all you normalize your words by replacing each letter with the corresponding key (e.g. replace every g, h and i with 4 and so on). You then construct a trie or some other prefix data structure to store words based on their nomalized representation. The rest is easy.

Upvotes: 2

Related Questions