- 0
Notifications Mark All Read
No New notification
- Login
- Get Prime
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++.
Problem Description
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.
Example :
Suppose the given array is :
Abcd
Abcdef
Abcdefgh
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.
C++ Code:
Output:
The matching Records are for Xyz are
Xyz
Xyz abc
Xyz abcde
********************************
No records found for Mr Xyz Abc
Login/Signup to comment