Trie (Prefix Tree)

Wildcard Search: search("c.t")

When we encounter a '.', we branch out to all children using DFS. If any branch leads to a match, return true.

Counting Variant: passCount & endCount

Each node stores two counters: passCount (how many words pass through this node) and endCount (how many words end here). This enables "count words with prefix" and "count exact matches."

Trie Node + Core Operations

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

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null)
                node.children[idx] = new TrieNode();  // create if missing
            node = node.children[idx];                // move down
        }
        node.isEnd = true;                          // mark end of word
    }

    boolean search(String word) {
        TrieNode node = traverse(word);
        return node != null && node.isEnd;          // must be end-of-word
    }

    boolean startsWith(String prefix) {
        return traverse(prefix) != null;            // just needs to exist
    }

    // Helper: walk down the trie following each char
    TrieNode traverse(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}

Wildcard Search (DFS for '.' characters)

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

boolean dfs(TrieNode node, String word, int i) {
    if (i == word.length()) return node.isEnd;

    char c = word.charAt(i);
    if (c == '.') {
        // wildcard: try every non-null child
        for (TrieNode child : node.children)
            if (child != null && dfs(child, word, i + 1))
                return true;
        return false;
    } else {
        int idx = c - 'a';
        if (node.children[idx] == null) return false;
        return dfs(node.children[idx], word, i + 1);
    }
}

Why O(L) per Operation?

Each operation (insert, search, startsWith) traverses at most L characters, where L is the length of the word or prefix. At each character, the work is O(1): check or create a child in a fixed-size array. Total: O(L) per operation — completely independent of dictionary size N.

Space: In the worst case (no shared prefixes), we store one node per character across all words. If N words each have average length L, the space is O(N * L). In practice, shared prefixes reduce this significantly.

Wildcard search: In the worst case with many '.' characters, the wildcard DFS may explore all branches, giving O(26^L) for a word of all dots. In practice, specific characters prune the search heavily.