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

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