Command Palette

Search for a command to run...

Hectal
Problem 19.1 · TrieMedium

Implement Trie (Prefix Tree)

PatternTrie (Prefix Tree)Combine Structures to Design

What it teaches: The trie itself: insert, search and startsWith.

Practise it on judges as “Implement Trie (Prefix Tree)”.

The problem

Design Trie with insert(word), search(word) (was this exact word inserted?) and startsWith(prefix) (was any word with this prefix inserted?). Words use lowercase letters.

Example 1

Input: insert apple; search apple; search app; startsWith app; insert app; search app
Output: true, false, true, true

Constraints

  • 1 ≤ length ≤ 2000
  • Up to 3 × 10⁴ calls

Pattern clues in the wording

  • → Prefix queries
  • → Dictionary of words

These clues point to Trie (Prefix Tree): Store words character by character in a tree so every prefix is a path you can walk in O(length).

Stuck? Take one hint at a time

Trie.java · starter
class Trie {
    public Trie() {}
    public void insert(String word) {}
    public boolean search(String word) { return false; }
    public boolean startsWith(String prefix) { return false; }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
ops = ["Trie","insert","search","search","startsWith","insert","search"]
args = [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
[null,null,true,false,true,null,true]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Array children · O(L) per call
1

Array children

Time O(L) per call Space O(total characters × 26)

Node with Node[26] and isWord. walk(s) returns the node at the end of s, or null.

Approach 1
class Trie {
    private static class Node {
        Node[] next = new Node[26];
        boolean isWord;
    }

    private final Node root = new Node();

    public Trie() {}

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

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

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

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

Verdict: Fast and simple.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Prefix that is not a word
  • Same word inserted twice

Mistakes people make

  • search returning true for prefixes.

Interview

Follow-up questions

How would you support delete?