mediumTries

Implement Trie (Prefix Tree)

Implement a trie supporting insert, search for a complete word, and prefix lookup.

LeetCode ↗

Work through the cases

3 examples

Input notation

One command per line: insert word, search word, or prefix word. Words use lowercase letters.

Expected result

true or false for each search or prefix command.

Case 1

Input

insert apple
search app
prefix app

Expected output

false
true

Case 2

Input

insert cat
search cat
prefix dog

Expected output

true
false

Case 3

Input

insert a
insert a
search a
search aa

Expected output

true
false

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Scanning every inserted word for each prefix query repeats work on shared prefixes. Letters are lowercase, so a 26-way tree can layer characters. Insertion walks (and creates) nodes and marks isEnd at the last one. Prefix search follows the same path; full-word search also checks the end flag.

Each node in the trie contains two parts:

1. An array of pointers to child nodes children. For this problem, the array length is 26, representing the number of lowercase English letters. children[0] corresponds to lowercase letter 'a', ..., and children[25] corresponds to lowercase letter 'z'. 2. A boolean field isEnd indicating whether the node is the end of a string.

### 1. Insert a String

We start from the root of the trie and insert the string. For the child node corresponding to the current character, there are two cases:

- The child node exists. Move along the pointer to the child node and continue processing the next character. - The child node does not exist. Create a new child node, record it in the corresponding position of the children array, then move along the pointer to the child node and continue searching for the next character.

Repeat the above steps until the last character of the string is processed, then mark the current node as the end of the string.

### 2. Search for a Prefix

We start from the root of the trie and search for the prefix. For the child node corresponding to the current character, there are two cases:

- The child node exists. Move along the pointer to the child node and continue searching for the next character. - The child node does not exist. This means the trie does not contain the prefix, so return a null pointer.

Repeat the above steps until a null pointer is returned or the last character of the prefix is searched.

If we search to the end of the prefix, it means the trie contains the prefix. Additionally, if the isEnd of the node corresponding to the end of the prefix is true, it means the trie contains the string.

The time complexity for inserting a string is O(m × |\Sigma|), and the time complexity for searching a prefix is O(m), where m is the length of the string and |\Sigma| is the size of the character set (26 in this problem). The space complexity is O(q × m × |\Sigma|), where q is the number of inserted strings.

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
    }

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

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        Trie node = searchPrefix(prefix);
        return node != null;
    }

    private Trie searchPrefix(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                return null;
            }
            node = node.children[idx];
        }
        return node;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.