package hackerrank.ctci;

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

/**
 * https://www.hackerrank.com/challenges/ctci-contacts
 */
public class Contacts {
    private static class Node {
        private final Map<Character, Node> children = new HashMap<>();
        private boolean word;
    }

    private static class IntRef {
        int count;
    }

    private static class Trie {
        private Node root = new Node();

        public void add(String str) {
            add(str, root, 0);
        }

        private static void add(String str, Node node, int idx) {
            if (idx == str.length()) {
                return;
            }
            char c = str.charAt(idx);
            if (node.children.containsKey(c)) {
                Node child = node.children.get(c);
                if (str.length() - 1 == idx) {
                    child.word = true;
                }
                add(str, child, idx + 1);
            } else {
                Node newNode = new Node();
                if (str.length() - 1 == idx) {
                    newNode.word = true;
                }
                node.children.put(c, newNode);
                add(str, newNode, idx + 1);
            }
        }

        private int find(String str) {
            IntRef ref = new IntRef();
            find(str, root, 0, ref);
            return ref.count;
        }

        private static void find(String str, Node node, int idx, IntRef ref) {
            if (idx == str.length()) {
                allChildren(node, ref);
                return;
            }
            char c = str.charAt(idx);
            if (node.children.containsKey(c)) {
                Node child = node.children.get(c);
                if (idx == str.length() - 1 && child.word) {
                    ref.count++;
                }
                find(str, child, idx + 1, ref);
            }
        }

        private static void allChildren(Node node, IntRef ref) {
            if (node == null) {
                return;
            }
            for (Map.Entry<Character, Node> child : node.children.entrySet()) {
                Node cn = child.getValue();
                if (cn.word) {
                    ref.count++;
                }
                allChildren(cn, ref);
            }
        }
    }

    private static void contact(Trie trie, String op, String contact) {
        if (op.equals("find")) {
            System.out.println(trie.find(contact));
        } else if (op.equals("add")) {
            trie.add(contact);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Trie trie = new Trie();
        for (int a0 = 0; a0 < n; a0++) {
            String op = in.next();
            String contact = in.next();
            contact(trie, op, contact);
        }
    }
}

@@ -23,56 +23,8 @@
 i;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A
 impo
@@ -45,16 +45,16 @@
 canner;%0A
+
 %0A/**%0A * 
@@ -190,29 +190,15 @@
 inal
- Map%3CCharacter,
  Node
-%3E
+%5B%5D
  chi
@@ -213,19 +213,16 @@
 new 
-HashMap%3C%3E()
+Node%5B27%5D
 ;%0A  
@@ -675,39 +675,41 @@
 ode.children
-.containsKey(c)
+%5Bc - 'a'%5D != null
 ) %7B%0A        
@@ -734,39 +734,41 @@
  = node.children
-.get(c)
+%5Bc - 'a'%5D
 ;%0A              
@@ -1102,23 +1102,27 @@
 dren
-.put(c,
+%5Bc - 'a'%5D =
  newNode
 );%0A 
@@ -1117,17 +1117,16 @@
  newNode
-)
 ;%0A      
@@ -1611,23 +1611,25 @@
 dren
-.containsKey(c)
+%5Bc - 'a'%5D != null
 ) %7B%0A
@@ -1674,15 +1674,17 @@
 dren
-.get(c)
+%5Bc - 'a'%5D
 ;%0A  
@@ -2022,34 +2022,12 @@
 or (
-Map.Entry%3CCharacter, 
 Node
-%3E
  chi
@@ -2048,19 +2048,8 @@
 dren
-.entrySet()
 ) %7B%0A
@@ -2068,35 +2068,76 @@
     
-Node cn = child.getValue();
+if (child == null) %7B%0A                    continue;%0A                %7D
 %0A   
@@ -2154,17 +2154,20 @@
    if (c
-n
+hild
 .word) %7B
@@ -2247,17 +2247,20 @@
 ildren(c
-n
+hild
 , ref);%0A

Update Contacts