Tries

We're going to make our own Contacts application! The application must perform two types of operations:

1. add name, where name is a string denoting a contact name. This must store name as a new contact in the application.
2. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting with partial and print the count on a new line.

Given n sequential add and find operations, perform each operation in order.

Input Format

Example:

Input: 4
add hack
add hackerrank
find hac
find hak
Output:2 0

Approach

Java

public class Tries {
    class Trie_Node {
        Trie_Node children[];
        int val = 0;

        Trie_Node() {
            children = new Trie_Node[26];

            for (int i = 0; i < 26; i++) {
                children[i] = null;
            }
        }
    }

    Trie_Node root;

    Tries() {
        root = new Trie_Node();
    }

    void add(String s) {
        Trie_Node temp = root;

        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            if (temp.children[index] == null)
                temp.children[index] = new Trie_Node();

            temp = temp.children[index];
            temp.val++;
        }
    }

    int find(String s) {

        Trie_Node temp = root;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            if (temp.children[index] == null)
                return 0;

            temp = temp.children[index];
        }

        return temp.val;
    }

    public static void main(String[] args) throws Exception {
        StringBuilder sb = new StringBuilder();
        Tries t = new Tries();

        int T = 4;
        String[][] arr = { { "add", "hack" }, { "add", "hackerrank" }, { "find", "hac" }, { "find", "hak" } };
        for (int i = 0; i < T; i++) {
            String s = arr[i][0];
            String s1 = arr[i][1];
            if (s.equals("add"))
                t.add(s1);
            else
                sb.append(t.find(s1)).append("\n");
        }
        System.out.println(sb.toString());
    }
}