Trie Basics

What is a Trie?

A Trie (also known as a prefix tree or dictionary tree) is a specialized multi-way tree structure where each node represents a single character. A path from the root to a designated terminal node represents a complete string.

Core Advantages:

• Complexity: Insertion and Search take $O(L)$, where $L$ is the length of the string.
• Prefix Matching: Retrieval by prefix takes $O(P)$, where $P$ is the length of the prefix.
• Vs. Hash Table: While using more memory, Tries outperform hash tables in alphabetical sorting and prefix-based queries.

Implementing a Trie (LeetCode 208)

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

    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null)
                cur.children[idx] = new TrieNode();
            cur = cur.children[idx];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) return false;
            cur = cur.children[idx];
        }
        return cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) return false;
            cur = cur.children[idx];
        }
        return true;
    }
}

Search with Wildcards (LeetCode 211)

Supporting the . character to match any one letter.

class WordDictionary {
    private TrieNode root = new TrieNode();

    public void addWord(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c - 'a'] == null)
                cur.children[c - 'a'] = new TrieNode();
            cur = cur.children[c - 'a'];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int idx, TrieNode node) {
        if (idx == word.length()) return node.isEnd;
        char c = word.charAt(idx);
        if (c != '.') {
            TrieNode next = node.children[c - 'a'];
            return next != null && dfs(word, idx + 1, next);
        }
        // '.' matches all existing branches
        for (TrieNode child : node.children) {
            if (child != null && dfs(word, idx + 1, child)) return true;
        }
        return false;
    }
}

Map Sum Pairs (LeetCode 677)

Each node maintains a value, and we compute the sum of values for all keys with a given prefix.

class MapSum {
    private TrieNode root = new TrieNode();

    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int val;
    }

    public void insert(String key, int val) {
        TrieNode cur = root;
        for (char c : key.toCharArray()) {
            if (cur.children[c - 'a'] == null) cur.children[c - 'a'] = new TrieNode();
            cur = cur.children[c - 'a'];
        }
        cur.val = val;
    }

    public int sum(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            if (cur.children[c - 'a'] == null) return 0;
            cur = cur.children[c - 'a'];
        }
        return dfsSum(cur);
    }

    private int dfsSum(TrieNode node) {
        if (node == null) return 0;
        int sum = node.val;
        for (TrieNode child : node.children) sum += dfsSum(child);
        return sum;
    }
}

The Deletion Algorithm

Deleting from a Trie involves three scenarios:

1. Word Missing: No action needed.
2. Word is a Prefix: Simply unset the isEnd flag.
3. Unique Leaf Path: Recursively remove nodes upward until a node with other children or an isEnd flag is encountered.

public boolean delete(String word) {
    return deleteHelper(root, word, 0);
}

private boolean deleteHelper(TrieNode node, String word, int idx) {
    if (idx == word.length()) {
        if (!node.isEnd) return false;
        node.isEnd = false;
        return isLeaf(node); // If it's a leaf, it can be pruned
    }
    int ci = word.charAt(idx) - 'a';
    if (node.children[ci] == null) return false;
    
    boolean shouldDeleteChild = deleteHelper(node.children[ci], word, idx + 1);
    if (shouldDeleteChild) {
        node.children[ci] = null;
        // Current node can be deleted only if it's not a terminal node 
        // and has no other children
        return !node.isEnd && isLeaf(node);
    }
    return false;
}

private boolean isLeaf(TrieNode node) {
    for (TrieNode c : node.children) if (c != null) return false;
    return true;
}

筋