Trie

Trie is a k-ary search tree. It can store a large amount of strings and provide efficient string search.

Trie & TrieNode

Trie generally has two data structures, one is Trie and the other is TrieNode. TrieNode is used to construct the entire tree, and Trie will only be one. TrieNode.terminates means that the path from root to this node is a word. In addition, TrieNode.character is not necessary, because the character represented by the node can be known from the children of the parent. Root does not represent any characters.

public class Trie {
    private final TrieNode root = new TrieNode();

    public Trie(ArrayList<String> list) {
        for (String word : list) {
            root.addWord(word);
        }
    }

    public Trie(String[] list) {
        for (String word : list) {
            root.addWord(word);
        }
    }

    public boolean contains(String prefix, boolean exact) {
        TrieNode lastNode = root;
        for (int i = 0; i < prefix.length(); i++) {
            lastNode = lastNode.getChild(prefix.charAt(i));
            if (lastNode == null) {
                return false;
            }
        }
        return !exact || lastNode.terminates();
    }

    public boolean contains(String prefix) {
        return contains(prefix, false);
    }

    public void addWord(String word) {
        root.addWord(word);
    }
}

public class TrieNode {
    private final HashMap<Character, TrieNode> children = new HashMap<>();
    private boolean terminates = false;
    private char character;

    public TrieNode() {
    }

    public TrieNode(char character) {
        this.character = character;
    }

    public char getChar() {
        return character;
    }

    public void addWord(String word) {
        if (word == null || word.isEmpty()) {
            return;
        }

        char firstChar = word.charAt(0);
        TrieNode child = getChild(firstChar);
        if (child == null) {
            child = new TrieNode(firstChar);
            children.put(firstChar, child);
        }

        if (word.length() > 1) {
            child.addWord(word.substring(1));
        } else {
            child.setTerminates(true);
        }
    }

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

    public boolean terminates() {
        return terminates;
    }

    public void setTerminates(boolean terminates) {
        this.terminates = terminates;
    }
}

Complexity

The time complexity required to build a dictionary is , where  is the length of word[i].

The time complexity required to search and insert a word is .

The space complexity is the number of all nodes, so it is .

Example

The example below shows what happens inside the Trie when a word is inserted. Green means the node’s terminates is set to true.

Reference

• Gayle Laakmann McDowell, Cracking the Coding Interview, 6th Edition.
• Trie, Wikipedia.