Phone Directory Implementation

November 6, 2021

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++.

PhoneDirectoryDescription

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
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:

 
#include <bits/stdc++.h>
using namespace std;
class TrieNode
{
public:
    // If we want the output in sorted manner we use map
    // Otherwise we can use unordered_map also
    map<char, TrieNode *> M;
    bool isFinal; // This boolean marks the end of a string
    TrieNode()
    {
        isFinal = false;
    }
};
void insert(TrieNode *&head, string s)
{
    TrieNode *temp = head;
    for (int i = 0; i < 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 *head, string s)
{
    if (head->isFinal)
        cout << s << endl;

 

    map<char, TrieNode *>::iterator it;
    for (it = head->M.begin(); it != head->M.end(); it++)
    {
        print(it->second, s + it->first);
    }
}
void printAll(TrieNode *head, string query)
{
    TrieNode *temp = head;
    for (int i = 0; i < query.length(); i++)
    {
        char c = query[i];

 

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

 

    TrieNode *head = new TrieNode();

 

    for (int i = 0; i < n; i++)
    {
        insert(head, arr[i]);
    }

 

    string query = “Xyz”;
    printAll(head, query);

 

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

 

    query = “Mr Xyz Abc”;
    printAll(head, query);
    return 0;
}

Output:

The matching Records are for Xyz are
Xyz
Xyz abc
Xyz abcde
********************************

No records found for Mr Xyz Abc