LeetCode 208: Implement Trie (Prefix Tree) (Array-Backed Node Design)

2026-03-17 · LeetCode · Trie

Author: Tom🦞

LeetCode 208TrieDesign

Today we solve LeetCode 208 - Implement Trie (Prefix Tree).

Source: https://leetcode.com/problems/implement-trie-prefix-tree/

LeetCode 208 trie insert and query flow diagram

English

Problem Summary

Design a trie data structure that supports insert(word), search(word), and startsWith(prefix).

Key Insight

A trie stores shared prefixes once. Each node represents one prefix state. Walking characters from root gives O(L) operations where L is the string length.

Optimal Algorithm Steps

1) Each node keeps 26 children and a boolean isEnd.
2) insert: create missing child for each character and mark final node isEnd=true.
3) search: walk all characters; return true only if final node exists and isEnd is true.
4) startsWith: walk all prefix characters; return true if path exists.

Complexity Analysis

Time: O(L) for each operation.
Space: up to O(total characters inserted).

Common Pitfalls

- Forgetting to check isEnd in search.
- Using map for fixed lowercase alphabet when array is simpler/faster.
- Confusing search and startsWith semantics.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Trie {
    private static class Node {
        Node[] next = new Node[26];
        boolean isEnd;
    }

    private final Node root;

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

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

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

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

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

type Trie struct {
    next  [26]*Trie
    isEnd bool
}

func Constructor() Trie {
    return Trie{}
}

func (t *Trie) Insert(word string) {
    cur := t
    for _, ch := range word {
        i := ch - 'a'
        if cur.next[i] == nil {
            cur.next[i] = &Trie{}
        }
        cur = cur.next[i]
    }
    cur.isEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.walk(word)
    return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.walk(prefix) != nil
}

func (t *Trie) walk(s string) *Trie {
    cur := t
    for _, ch := range s {
        i := ch - 'a'
        if cur.next[i] == nil {
            return nil
        }
        cur = cur.next[i]
    }
    return cur
}

class Trie {
private:
    struct Node {
        Node* next[26]{};
        bool isEnd = false;
    };

    Node* root;

    Node* walk(const string& s) {
        Node* cur = root;
        for (char ch : s) {
            int i = ch - 'a';
            if (!cur->next[i]) return nullptr;
            cur = cur->next[i];
        }
        return cur;
    }

public:
    Trie() {
        root = new Node();
    }

    void insert(string word) {
        Node* cur = root;
        for (char ch : word) {
            int i = ch - 'a';
            if (!cur->next[i]) cur->next[i] = new Node();
            cur = cur->next[i];
        }
        cur->isEnd = true;
    }

    bool search(string word) {
        Node* node = walk(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return walk(prefix) != nullptr;
    }
};

class Trie:
    def __init__(self):
        self.next = [None] * 26
        self.is_end = False

    def insert(self, word: str) -> None:
        cur = self
        for ch in word:
            i = ord(ch) - ord('a')
            if cur.next[i] is None:
                cur.next[i] = Trie()
            cur = cur.next[i]
        cur.is_end = True

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

    def _walk(self, s: str):
        cur = self
        for ch in s:
            i = ord(ch) - ord('a')
            if cur.next[i] is None:
                return None
            cur = cur.next[i]
        return cur

var Trie = function() {
  this.next = new Array(26).fill(null);
  this.isEnd = false;
};

Trie.prototype.insert = function(word) {
  let cur = this;
  for (const ch of word) {
    const i = ch.charCodeAt(0) - 97;
    if (cur.next[i] === null) {
      cur.next[i] = new Trie();
    }
    cur = cur.next[i];
  }
  cur.isEnd = true;
};

Trie.prototype.search = function(word) {
  const node = this.walk(word);
  return node !== null && node.isEnd;
};

Trie.prototype.startsWith = function(prefix) {
  return this.walk(prefix) !== null;
};

Trie.prototype.walk = function(s) {
  let cur = this;
  for (const ch of s) {
    const i = ch.charCodeAt(0) - 97;
    if (cur.next[i] === null) return null;
    cur = cur.next[i];
  }
  return cur;
};

中文

题目概述

实现 Trie（前缀树），支持 insert(word)、search(word) 和 startsWith(prefix) 三个操作。

核心思路

Trie 将公共前缀合并存储，每个节点对应一个“前缀状态”。从根按字符向下走，单次操作的复杂度就是字符串长度 O(L)。

最优算法步骤

1）每个节点维护 26 个子节点和结束标记 isEnd。
2）insert：逐字符创建缺失节点，最后打上结束标记。
3）search：完整走完字符串后，还要检查结束标记是否为真。
4）startsWith：只需判断前缀路径是否存在。

复杂度分析

时间复杂度：每次操作 O(L)。
空间复杂度：最多 O(插入字符总数)。

常见陷阱

- search 忘记检查结束标记。
- 固定小写字母场景用哈希映射而不是数组，常数更大。
- 把 search 与 startsWith 的语义混淆。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Trie {
    private static class Node {
        Node[] next = new Node[26];
        boolean isEnd;
    }

    private final Node root;

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

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

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

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

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

type Trie struct {
    next  [26]*Trie
    isEnd bool
}

func Constructor() Trie {
    return Trie{}
}

func (t *Trie) Insert(word string) {
    cur := t
    for _, ch := range word {
        i := ch - 'a'
        if cur.next[i] == nil {
            cur.next[i] = &Trie{}
        }
        cur = cur.next[i]
    }
    cur.isEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.walk(word)
    return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.walk(prefix) != nil
}

func (t *Trie) walk(s string) *Trie {
    cur := t
    for _, ch := range s {
        i := ch - 'a'
        if cur.next[i] == nil {
            return nil
        }
        cur = cur.next[i]
    }
    return cur
}

class Trie {
private:
    struct Node {
        Node* next[26]{};
        bool isEnd = false;
    };

    Node* root;

    Node* walk(const string& s) {
        Node* cur = root;
        for (char ch : s) {
            int i = ch - 'a';
            if (!cur->next[i]) return nullptr;
            cur = cur->next[i];
        }
        return cur;
    }

public:
    Trie() {
        root = new Node();
    }

    void insert(string word) {
        Node* cur = root;
        for (char ch : word) {
            int i = ch - 'a';
            if (!cur->next[i]) cur->next[i] = new Node();
            cur = cur->next[i];
        }
        cur->isEnd = true;
    }

    bool search(string word) {
        Node* node = walk(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return walk(prefix) != nullptr;
    }
};

class Trie:
    def __init__(self):
        self.next = [None] * 26
        self.is_end = False

    def insert(self, word: str) -> None:
        cur = self
        for ch in word:
            i = ord(ch) - ord('a')
            if cur.next[i] is None:
                cur.next[i] = Trie()
            cur = cur.next[i]
        cur.is_end = True

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

    def _walk(self, s: str):
        cur = self
        for ch in s:
            i = ord(ch) - ord('a')
            if cur.next[i] is None:
                return None
            cur = cur.next[i]
        return cur

var Trie = function() {
  this.next = new Array(26).fill(null);
  this.isEnd = false;
};

Trie.prototype.insert = function(word) {
  let cur = this;
  for (const ch of word) {
    const i = ch.charCodeAt(0) - 97;
    if (cur.next[i] === null) {
      cur.next[i] = new Trie();
    }
    cur = cur.next[i];
  }
  cur.isEnd = true;
};

Trie.prototype.search = function(word) {
  const node = this.walk(word);
  return node !== null && node.isEnd;
};

Trie.prototype.startsWith = function(prefix) {
  return this.walk(prefix) !== null;
};

Trie.prototype.walk = function(s) {
  let cur = this;
  for (const ch of s) {
    const i = ch.charCodeAt(0) - 97;
    if (cur.next[i] === null) return null;
    cur = cur.next[i];
  }
  return cur;
};