Shortest Unique Prefix

Find shortest unique prefix to represent each word in the list.

Example:

Input: [zebra, dog, duck, dove]
Output: {z, dog, du, dov}
where we can see that
zebra = z
dog = dog
duck = du
dove = dov

public class Solution {
    static class TrieNode {
        char data;
        boolean isTerminating;
        TrieNode children[];
        int wordsPassingthrough;

        public TrieNode(char data) {
            this.data = data;
            isTerminating = false;
            children = new TrieNode[26];
            wordsPassingthrough = 0;
        }
    }

    static public class Trie {
        TrieNode root;
        public int count;

        public Trie() {
            root = new TrieNode('\0');
        }

        public int search(String word) {
            return search(root, word, -1);
        }

        int search(TrieNode node, String word, int level) {
            if (word.length() == 0)
                return level;
            if (node.wordsPassingthrough == 1 && node != this.root)
                return level;
            int childIndex = word.charAt(0) - 'a';
            return search(node.children[childIndex], word.substring(1), level + 1);
        }

        public void add(String word) {
            add(root, word);
        }

        void add(TrieNode root, String word) {
            if (word.length() == 0) {
                root.isTerminating = true;
                return;
            }
            int childIndex = word.charAt(0) - 'a';
            if (root.children[childIndex] == null)
                root.children[childIndex] = new TrieNode(word.charAt(0));
            root.wordsPassingthrough++;
            add(root.children[childIndex], word.substring(1));
        }
    }

    public String[] prefix(String[] A) {
        Trie trie = new Trie();
        for (String x : A)
            trie.add(x);
        String[] ans = new String[A.length];
        for (int i = 0; i < A.length; i++) {
            int index = trie.search(A[i]);
            ans[i] = A[i].substring(0, index + 1);
        }
        return ans;
    }
}