Start practising

Implement Trie (Prefix Tree)

Medium Tries Basics Original on LeetCode

Implement Trie (Prefix Tree) is a medium tries problem solved with the basics pattern. The best approach, optimal (trie nodes with 26 children), runs in O(L) per operation time and O(total characters · 26) space. Below are 2 approaches in Java, from hash set of words up.

Problem

Implement a trie (prefix tree) with three operations: insert(word), search(word) (was this exact word inserted?) and startsWith(prefix) (was any word with this prefix inserted?).

Examples

Example 1

Input
insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")
Output
true, false, true, true

Constraints

  • Words and prefixes use lowercase letters, length 1 to 2000.
  • Up to 3 * 10^4 calls.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Hash set of wordsO(n · L) for startsWithO(total characters)
Optimal (trie nodes with 26 children)O(L) per operationO(total characters · 26)

1Hash set of words

TimeO(n · L) for startsWith
SpaceO(total characters)

Store the words in a set. search is O(L) on average, but startsWith must scan every word.

  1. insert: add to set. search: contains.
  2. startsWith: check each word's prefix.
Java
class Trie {
    private final Set<String> words = new HashSet<>();

    public void insert(String word) { words.add(word); }

    public boolean search(String word) { return words.contains(word); }

    public boolean startsWith(String prefix) {
        for (String w : words) if (w.startsWith(prefix)) return true;
        return false;
    }
}

2Optimal (trie nodes with 26 children)

TimeO(L) per operation
SpaceO(total characters · 26)

Walk down one node per character, creating nodes on insert. search needs the walk to succeed and the final node to be marked as a word end; startsWith only needs the walk to succeed.

  1. insert: for each char, create the child if missing; move; mark end.
  2. search: walk; return node != null && node.end.
  3. startsWith: walk; return node != null.
Java
class Trie {
    private static class Node {
        Node[] next = new Node[26];
        boolean end;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
            cur = cur.next[c - 'a'];
        }
        cur.end = true;
    }

    public boolean search(String word) {
        Node n = walk(word);
        return n != null && n.end;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    private Node walk(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.next[c - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }
}

Edge cases to test

  • A word that is a prefix of another (app vs apple)
  • search for a prefix that exists but is not a full word

Hints

Hint 1

Each node has 26 child slots and a flag that marks the end of a word.

FAQ

What is the best time complexity for Implement Trie (Prefix Tree)?

Optimal (trie nodes with 26 children) runs in O(L) per operation time and O(total characters · 26) extra space.

Which pattern does Implement Trie (Prefix Tree) use?

It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie ll.

Is there a brute force solution for Implement Trie (Prefix Tree)?

Yes. Hash set of words takes O(n · L) for startsWith time and O(total characters) space. Store the words in a set.

Which edge cases should I test for Implement Trie (Prefix Tree)?

A word that is a prefix of another (app vs apple); search for a prefix that exists but is not a full word.