Implement Trie (Prefix Tree)

Problem

Implement a trie with insert(word), search(word) (exact match), and startsWith(prefix).

Constraints

• 1 ≤ word/prefix length ≤ 2000
• methods called ≤ 3·10⁴ times

Approach — Core Patterns

This is a Core Patterns problem. The idea: pick the data structure best matched to the constraints and solve it in one clean pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: see the walkthrough below.

Solution code

Python

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return '$' in node

    def startsWith(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return False
            node = node[ch]
        return True

Java

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

    public void insert(String word) {
        TrieNode n = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (n.children[i] == null) n.children[i] = new TrieNode();
            n = n.children[i];
        }
        n.end = true;
    }
    public boolean search(String word)      { TrieNode n = find(word); return n != null && n.end; }
    public boolean startsWith(String pfx)   { return find(pfx) != null; }
    private TrieNode find(String s) {
        TrieNode n = root;
        for (char c : s.toCharArray()) {
            n = n.children[c - 'a'];
            if (n == null) return null;
        }
        return n;
    }
}

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.