Phone Directory Implementation
Phone Directory Implementation in C++
This problem is basically about implementing the search feature that is found in our mobile phones contacts app. Whenever we enter a partial name or a string in the search bar, it lists out all the possible contacts which have same prefix. Here is explanation of Phone Directory Implementation in C++.
We are given a array of n strings. We are also given another string. We have to print all strings from the array who have some prefix exactly matching with the given string.
Suppose the given array is :
Phone Directory in C++ Algorithm:
We can solve the problem using tries. You can learn about Trie Data Structure from here.
Step 1 Insertion of Strings in the Trie
- Create a class consisting of a map that points to child nodes and a boolean variable isFinal. The boolean variable is used to mark the end of a string since we can have strings with common prefixes in the given array ( eg aaa, aaaa) . It is set to false by default.
- Iterate over the string array and add strings to the trie.
- After adding the last character mark the isFinal boolean as true.
Step 2 Printing the matching Strings
The print function is basically a extension of the search functionality that we have implemented in basic trie.
- Iterate over the trie and keep moving till there are matching nodes for the characters of the query string.
- If we encounter a character such that there is no child node present , this means we have no matching string and we can return from here.
- After matching all the characters we basically have to generate all possible strings using recursion. The isFinal variable will come handy when we want to print the string.
The matching Records are for Xyz are
No records found for Mr Xyz Abc