Skip to content

# HackerRank Solutions – Tries – Contacts – Java Solution

All credits to Rodney Shaghoulian for this simple solution for the HackerRank challenge – Tries – Contacts. This solution is written in Java.

// Author: Rodney Shaghoulian
// Github: github.com/RodneyShag

import java.util.Scanner;
import java.util.HashMap;

public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
Trie trie = new Trie();
for (int i = 0; i < n; i++) {
String operation = scan.next();
String contact   = scan.next();
if (operation.equals("add")) {
trie.add(contact);
} else if (operation.equals("find")) {
System.out.println(trie.find(contact));
}
}
scan.close();
}
}

/* Based loosely on tutorial video in this problem */
class TrieNode {
private HashMap<Character, TrieNode> children = new HashMap<>();
public int size = 0; // this was the main trick to decrease runtime to pass tests.

public void putChildIfAbsent(char ch) {
children.putIfAbsent(ch, new TrieNode());
}

public TrieNode getChild(char ch) {
return children.get(ch);
}
}

class Trie {
TrieNode root = new TrieNode();

public void add(String str) {
TrieNode curr = root;
for (char ch : str.toCharArray()) {
curr.putChildIfAbsent(ch);
curr = curr.getChild(ch);
curr.size++;
}
}

public int find(String prefix) {
TrieNode curr = root;
for (char ch : prefix.toCharArray()) {
curr = curr.getChild(ch);
if (curr == null) {
return 0;
}
}
return curr.size;
}
}
See also  Plus One Linked List - Leetcode Challenge - Python Solution

This site uses Akismet to reduce spam. Learn how your comment data is processed.