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 :

string arr[5] = {“Abcd”, “Abcdef”, “Xyz”, “Abcdefgh”, “Xyz abc”}
Query string is :
string query = “Abcd”
The output should be :
The matching Records are for Abcd  are

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:

#include <bits/stdc++.h>
using namespace std;
class TrieNode
    // If we want the output in sorted manner we use map
    // Otherwise we can use unordered_map also
    map<charTrieNode *> M;
    bool isFinal; // This boolean marks the end of a string
        isFinal = false;
void insert(TrieNode *&headstring s)
    TrieNode *temp = head;
    for (int i = 0i < s.length(); i++)
        char c = s[i];
        if (temp->M.find(c== temp->M.end())
            temp->M[c] = new TrieNode();


        temp = temp->M[c];
    temp->isFinal = true;
// Recusive check all nodes (DFS)
void print(TrieNode *headstring s)
    if (head->isFinal)
        cout << s << endl;


    map<charTrieNode *>::iterator it;
    for (it = head->M.begin(); it != head->M.end(); it++)
        print(it->seconds + it->first);
void printAll(TrieNode *headstring query)
    TrieNode *temp = head;
    for (int i = 0i < query.length(); i++)
        char c = query[i];


        if (temp->M.find(c== temp->M.end())
            cout << “No records found “
                 << ” for “ << query << endl;
        temp = temp->M[c];
    cout << “The matching Records are for “ << query << ” are” << endl;
int main()
    int n = 5;
    string arr[5] = {“Mr Abc”“Xyz”“Xyz abc”“abcd ““Xyz abcde”};


    TrieNode *head = new TrieNode();


    for (int i = 0i < ni++)


    string query = “Xyz”;


    cout << “********************************” << endl
         << endl;


    query = “Mr Xyz Abc”;
    return 0;


The matching Records are for Xyz are
Xyz abc
Xyz abcde

No records found for Mr Xyz Abc