How to implement PhoneBook using tries data structure.

Design a data structure to store your contacts: Names of people along with their phone numbers.The data structure should be able to do the following quickly:

  • Add contacts.
  • Lookup the phone number by name.
  • Determine who is calling given their phone number.

To do that:

To implement this we will be using HashMap and Trie data structure. Trie data help us to search and provide suggestion on basis of keystroke entered. Once we select any contact name we can search in hashmap.

Generally search query on a Trie is to determine whether the string is present or not in the trie, but in this case we will find all the strings with each prefix of ‘str’. From a Trie node, visit adjacent Trie nodes and do this recursively until there are no more adjacent. This recursive function will take 2 arguments one as Trie Node which points to the current Trie Node being visited and other as the string which stores the string found so far with prefix as ‘str’.

Each Trie Node stores a boolean variable ‘isLast’ which is true if the node represents end of a contact(word).

User will enter the string character by character and we need to display suggestions with the prefix formed after every entered character.
So one approach to find the prefix starting with the string formed is to check if the prefix exists in the Trie, if yes then call the getConstacts() function. In this approach after every entered character we check if the string exists in the Trie.
Instead of checking again and again, we can maintain a pointer prevNode‘ that points to the TrieNode which corresponds to the last entered character by the user, now we need to check the child node for the ‘prevNode’ when user enters another character to check if it exists in the Trie. If the new prefix is not in the Trie, then all the string which are formed by entering characters after ‘prefix’ can’t be found in Trie too. So we break the loop that is being used to generate prefixes.

So here we create a PhoneBookDirectory class which contain a Hashmap and Trie. When we call add contact we are adding name and phoneno to hashmap and name to Trie. so we can get suggestion on basis of entered keystroke.

So here i entered Ricky, so it will list all contacts start with R, Ri,Ric,Rick,Ricky.

Angular,Vuejs,Android,Java,Git developer. i am nerd who want to learn new technologies, goes in depth.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store