Trie

Trie (Prefix Tree)

1. Introduction

Trie (Prefix Tree) is a useful data structure for storing prefix of strings and retrieval of string based on prefix

2. Implementation

public class Trie {
    class TrieNode {
        char val;
        TrieNode[] childNode;
        boolean isWord;

        public TrieNode() {
            childNode = new TrieNode[26];
        }
    }

    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        if (word == null || word.length() == 0) {
            return;
        }

        TrieNode node = root;

        for (char c : word.toCharArray()) {
            int index = c - 'a';

            if (node.childNode[index] == null) {
                node.childNode[index] = new TrieNode();
                node.childNode[index].val = c;
            }
            node = node.childNode[index];
        }
        node.isWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        if (word == null || word.length() == 0) {
            return false;
        }

        TrieNode node = root;

        for (char c : word.toCharArray()) {
            int index = c - 'a';

            if (node.childNode[index] == null) {
                return false;
            }
            else {
                node = node.childNode[index];
            }
        }
        return node.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) {
            return false;
        }

        TrieNode node = root;

        for (char c : prefix.toCharArray()) {
            int index = c - 'a';

            if (node.childNode[index] == null) {
                return false;
            }
            else {
                node = node.childNode[index];
            }
        }
        return true;
    }
}

3. Time & Space Complexity

1. insert(): O(L), where L is the length of word to be inserted

2. search(): O(L)

3. Space: O(size^L), size is the number of childeNode for each trie node. Normally, we define size as 26 if we only store alphabetical letters. Sometimes we may define size as 256 if we assume input is ASCII

4. Thoughts

1. Trie VS HashMap: Trie will be space efficient to solve store things that have common prefixes (e.g SSN, phone number), while lots of hash collisions will happen as hashMap increases in size.

2. By changing the structure of trieNode a little bit, we can use trie to do things like Google Suggestion (Add a minHeap to node), AutoComplete(Add a HashSet or List of Strings with the prefix), etc

3. Trie can also solve suffix problem (Distinct Substring)

5. Interview Questions

1. Trie from GeeksforGeeks

2. Trie Leetcode