LeetCode 208. Implement Trie (Prefix Tree)

Posted on In , Views:

🧩 Problem Description

A trie (pronounced try) or prefix tree is a tree data structure used to efficiently store and search strings in a dataset of strings.

Implement the Trie class:

  • Trie() initializes the object.
  • void insert(String word) inserts the string word into the trie.
  • boolean search(String word) returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) returns true if there is a previously inserted string word that starts with the given prefix.

💬 Example

1
2
3
4
5
6
Input:
["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]

Output:
[null,null,true,false,true,null,true]

💡 Approach: Trie Node Structure

We build a tree where each node contains up to 26 children (for each lowercase letter).
Each node also keeps a boolean flag isEnd to mark the end of a word.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Trie {
    class TrieNode {
        TrieNode[] children;
        boolean isEnd;

        TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public 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();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }
}

⏱ Complexity Analysis

  • Insert: O(L), where L = length of the word
  • Search: O(L)
  • StartsWith: O(P), where P = length of the prefix
  • Space: O(N * L), where N = number of words, L = average word length

✍️ Summary

  • Trie is a powerful data structure for string searching.
  • Operations are efficient: O(L).
  • Widely used in autocomplete, spell check, IP routing, and word games.

Related problems:

  • lc-211 — Design Add and Search Words Data Structure
  • lc-212 — Word Search II
  • lc-648 — Replace Words
  • lc-720 — Longest Word in Dictionary