# HackerRank Contacts problem solution

In this HackerRank Contacts problem, we need to make a list that must add name and find partial string in the list.

## Problem solution in Python programming.

```class node2(dict) :
__slots__ = ['numDescendants']
def __init__(self) :
self.numDescendants = 0
def addChild(self, child) :     # child is a character
self[child] = node2()
self.numDescendants += 1
def getNumDescendants(self) :
return self.numDescendants
def incNumDescendants(self) :
self.numDescendants += 1

class Contacts() :
def __init__(self) :
self.root = node2()

def Helper(currNode, suffix) :
if len(suffix)==0 :
else :
if suffix[0] in currNode :
currNode.incNumDescendants()
Helper(currNode[suffix[0]], suffix[1:])
else :
Helper(currNode[suffix[0]], suffix[1:])

currNode = self.root
Helper(currNode, name)

def findName(self, prefix) :
def findPrefix(currNode, prefix) :
if len(prefix)==0 :
return currNode
else :
if prefix[0] in currNode :
return findPrefix(currNode[prefix[0]], prefix[1:])
return -1

nameLoc = findPrefix(self.root, prefix)
if nameLoc==-1 :
print(0)
else :
print(nameLoc.getNumDescendants())
return

a = Contacts()
numLines = int(input())
while numLines > 0 :
command = input()
if command[0]=='a' :
elif command[0]=='f' :
a.findName(command[5:])
numLines -= 1```

## Problem solution in Java Programming.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

/*
* Complete the contacts function below.
*/

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws Exception{

HashMap<String, Integer> map = new HashMap<String, Integer>();

for (int i = 0; i < numQueries; i++){

for (int j = 1; j <= data[1].length(); j++){
String sub = data[1].substring(0, j);
if (map.get(sub) == null){
map.put(sub, 1);
} else {
map.put(sub, map.get(sub) + 1);
}
}
} else { //query matches
if (map.get(data[1]) == null){
System.out.println(0);
} else {
System.out.println(map.get(data[1]));
}

}
}
}
}```

## Problem solution in C++ programming.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

typedef struct node
{
char data;
node* next[26] = { NULL };
bool delimiter;
int total;

node()
{
for(int i = 0; i < 26; i ++)
next[i] = NULL;
delimiter = false;
total = 0;
}

}node;

{
for(int i = 0; i < size; i++)
{
int index = toadd[i] - 'a';
if(root->next[index] == NULL)
{
node *newnode = new node;
newnode->total = newnode->total + 1;
if(i == size - 1)
newnode->delimiter = true;
root->next[index] = newnode;
}
else
{
node *temp =  root->next[index];
temp->total = temp->total + 1;
if(i == size - 1)
temp->delimiter = true;
}
root = root->next[index];
}
}
void Find(node *root, string tofind)
{
int size =  tofind.size();
for(int i = 0; i < size; i++)
{
int index = tofind[i] - 'a';
if(root->next[index] == NULL)
{
cout<<0<<endl;
return;
}
else
{
root =  root->next[index];
}
}
if(root == NULL)
{
cout<<0<<endl;
return;
}
else
cout<<root->total<<endl;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int noofcommands = 0;
cin>>noofcommands;

node *root = new node;
root->data = '#';

for(int i = 0; i < noofcommands; i++)
{
string operation;
cin>>operation;
{
}
else
{
string tofind;
cin>>tofind;
Find(root, tofind);
}
}
return 0;
}```

## Problem solution in C programming.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct node_t{
char data;
struct node_t *children[26]; //One pointer to node per alphabet
int words;
int prefixes;
}node;

node *create_node(char data){
node *t = (node *)malloc(sizeof(node));

if(t)
{
memset(t, 0, sizeof(node));
t->data = data;
}
return t;
}

int find_prefix(node *root, char *prefix){
char c = *prefix;

if(root == NULL){
return 0;
}

if(root->data == '0'){ //This is the root of the trie
return find_prefix(root->children[c - 'a'], prefix);
}

else if(root->data == c){
prefix++;
if(*prefix == '\0'){ //We're done searching
return root->prefixes;
}
else{
return find_prefix(root->children[*prefix - 'a'], prefix);
}
}
printf("Did not find a match\n");
return 0;
}

//Assumes all input chars are lower case
char c = *str;
//printf("char: %c, diff: %d\n",c, c - 'a');
if(root == NULL){
printf("Root is null\n");
return;
}

if(c == '\0'){
printf(" Should never come here\n");
return;
}

if(root->children[c - 'a'] == NULL){
root->children[c - 'a'] = create_node(*str);
//printf("Created the child\n");
if(root->children[c - 'a'] == NULL){
printf("Failed to create node\n");
return;
}
}

root->children[c - 'a']->prefixes++;

str = str + 1;
//printf("child: %llu, data: %c\n", (unsigned long long)root->children[c - 'a'], root->children[c - 'a']->data);
//printf("str: %c\n",*str);
if(*str == '\0'){  //We have reached the end of the word
root->words++;
return;
}
}

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int num_ops;
int i = 0;
char op[5];
char str[28];

node *root = create_node('0');
if(root == NULL){
printf("Main: root is NULL\n");
return 0;
}

scanf("%d", &num_ops);
while(i < num_ops){
scanf("%s %s", op, str );
}
else if(!strcmp(op, "find")){
printf("%d\n", find_prefix(root, str));
}
i++;
}

return 0;
}```

## Problem solution in JavaScript programming.

```function processData(input) {
var lines = input.split("\n");
var operations = lines[0];
var root = createNode();

if (operations < 1 || operations > Math.pow(10, 5))
{
console.log(0);
return;
}

for (var i=1; i<=operations; i++)
{
var op = lines[i].split(" ");
var contact = op[1].toLowerCase();
var invalid = (contact.length < 1 || contact.length > 21);

switch (op[0])
{
if (!invalid)
break;

case "find":
console.log((invalid ? 0 : findPartial(contact)));

break;
}
}

function createNode()
{
// children, numberOfChildren, endOfContact
return [{}, 0, 0];
}

{
var pn = root;
for (var i=0; i<name.length; i++)
{
var c = name[i];

if (!pn[0][c])
pn[0][c] = createNode();

pn[0][c][1]++;
pn = pn[0][c];
}

// set end of contact name
pn[2] = 1;
}

function findPartial(str)
{
var pn = root;

for (var i=0; i<str.length; i++)
{
var c = str[i];

if (!pn[0][c])
{
return 0;
}

pn = pn[0][c];
}

// return count;
return pn[1];
}
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});```