Implement a phone directory

The first line contains a single integer ‘T’ denoting the number of test cases. The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array/list. The second line contains ‘N’ single space-separated strings denoting the contacts of the given array/list or contact list. The third line contains a single string denoting the query string.

For each test case, for the given query string you need to print all the possible contacts or suggestions that are present in the given directory corresponding to each entered character in the given query string. If no suggestions are found then the message “No suggestions found” is printed.

In the first test case, The suggestions for “c” is {“cod”, “coding”, “codding”, “code”, “coly”}. The suggestions for “co” is {“cod”, “coding”, “codding”, “code”, “coly”}. The suggestions for “cod” is {“cod”, “coding”, “codding”, “code”, “coly”}. The suggestion for “codi” is {“coding”}. The suggestion for “codin” is {“coding”}. The suggestion for “coding” is {“coding”}. In the second test case, The suggestion for “n” is {“ninjas”}. The suggestion for “ni” is {“ninjas”}. The suggestion for “nin” is {“ninjas”}. The suggestion for “ninj” is {“ninjas”}. The suggestion for “ninja” is {“ninjas”}.

In the first test case, The suggestion for “c” is {“coding”}. For the rest of the letters, there are no suggestions. In the second test case, The suggestion for “a” is {“ab”, “abc”}. In the third test case, no suggestions are found.

Trie + HashMap

A search query on a Trie is being used to determine whether the string is present or not in the trie, but in this case, we are asked to find all the strings with each prefix of ‘str’. This is equivalent to doing a DFS traversal on a graph.

From a Trie node, we need to visit adjacent Trie nodes and do this recursively until there is no more adjacent. This recursive function will take 2 arguments one as Trie Node which points to the current Trie Node being visited and the other as the string which stores the string found so far with prefix as ‘str’. We are creating an unordered_map where each alphabet points to a trie node.

Each Trie Node stores a boolean variable “isEnd” which becomes true if the node represents the end of contact or element of the given contact list. It is nothing but a variable that signifies that we don’t need to move forward to do a search because we reached the end of the particular word of the contactList.

Our approach is to find the prefix starting with the string formed is to check if the prefix exists in the Trie, if yes then call the display function which will display all the corresponding suggestions.
After every entered character we check if the string exists in the Trie.
We do not need to check again and again, so to avoid that we can maintain a pointer “PREV” that points to the TrieNode which corresponds to the last entered character by the user, now we need to check the child node for the “PREV” when the user enters another character to check if it exists in the Trie.
If the new prefix is not in the Trie, then all the strings which are formed by entering characters after the ‘prefix’ can’t be found in Trie too. So we break the loop because, for all the remaining characters, it’s not possible to find suggestions anymore.

Time Complexity

O(N * (W ^ 2)), where ‘N’ is the number of elements in the given array/list and ‘W’ is the average length of the string.

Consider an example when our word list will be like this :

{“a”,”aa”,”aaa”,”aaaa”,”aaaaa”,”aaaaaa”,”aaaaaa”} and we are looking for suggestions for the query string “aaaaaa”.

So for inserting the given contact list into trie will take O(N*W) time. And secondly, in order to store the suggestions, we’ll include all the lists for every character of the given prefix.

For example, Now considering all the W characters in the prefix and traversing all the N words which will take O(N*W), and combining both of these will result in O(W*(N*W)) time. So the overall time complexity will be O(N*(W^2)).

Space Complexity

O(N * W), where ‘N’ is the number of elements in the given array/list and ‘W’ is the average length of the string.

Since for each character in the prefix of the intermediate strings we are storing a map for its children where each alphabet points to a trie node resulting in taking the space for ‘W’ characters as O(N * W) space since we are looking for each string in the given word list.

So the overall space complexity will be O(N * W).

Implement a phone directory

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation to Sample Input 1 :

Sample Input 2 :

Sample Output 2 :

Explanation to Sample Input 2 :