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 addName(self, name) :
def Helper(currNode, suffix) :
if len(suffix)==0 :
currNode.addChild('') # termination character
else :
if suffix[0] in currNode :
currNode.incNumDescendants()
Helper(currNode[suffix[0]], suffix[1:])
else :
currNode.addChild(suffix[0])
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' :
a.addName(command[4:])
elif command[0]=='f' :
a.findName(command[5:])
numLines -= 1Problem 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{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int numQueries = Integer.parseInt(br.readLine());
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < numQueries; i++){
String[] data = br.readLine().split(" ");
if (data[0].equals("add")){
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;
void Add(node *root, string toadd)
{
int size = toadd.size();
for(int i = 0; i < size; i++)
{
int index = toadd[i] - 'a';
if(root->next[index] == NULL)
{
node *newnode = new node;
newnode->data = toadd[i];
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;
if(operation.compare("add") == 0)
{
string toadd;
cin>>toadd;
Add(root, toadd);
}
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
void add_word(node *root, char *str){
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;
}
add_word(root->children[c - 'a'], str);
}
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 );
//printf("Read: %s %s\n", op, str);
if(!strcmp(op, "add")){
add_word(root, 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])
{
case "add":
if (!invalid)
addContact(contact);
break;
case "find":
console.log((invalid ? 0 : findPartial(contact)));
break;
}
}
function createNode()
{
// children, numberOfChildren, endOfContact
return [{}, 0, 0];
}
function addContact(name)
{
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);
});
0 Comments