AlgoViz Lab交互式算法学习
Algorithms first

实现 Trie (前缀树) · 交互式算法学习

实现 Trie 的插入、完整词搜索和前缀搜索。

#208 · 字典树

实现 Trie (前缀树)

Implement Trie (Prefix Tree)

测试用例insert apple; search apple; startsWith app
树 / 图3 个关键状态
步骤 1沿 a→p→p→l→e 创建节点。insert
apple
推荐

前缀树节点

时间 每次 O(L)空间 O(总字符)

每个字符是一条边，节点标记是否为完整词结尾。

1class Trie {2  constructor() {3    this.root = {}4  }5  insert(w) {6    let n = this.root;7    for (const c of w) n = n[c] ??= {};8    n.end = true9  }10  walk(w) {11    let n = this.root;12    for (const c of w) {13      n = n[c];14      if (!n) return null15    }16    return n17  }18  search(w) {19    return !!this.walk(w)?.end20  }21  startsWith(p) {22    return !!this.walk(p)23  }24}
多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1class Trie {2    private Trie[] children;3    private boolean isEnd;4 5    public Trie() {6        children = new Trie[26];7    }8 9    public void insert(String word) {10        Trie node = this;11        for (char c : word.toCharArray()) {12            int idx = c - 'a';13            if (node.children[idx] == null) {14                node.children[idx] = new Trie();15            }16            node = node.children[idx];17        }18        node.isEnd = true;19    }20 21    public boolean search(String word) {22        Trie node = searchPrefix(word);23        return node != null && node.isEnd;24    }25 26    public boolean startsWith(String prefix) {27        Trie node = searchPrefix(prefix);28        return node != null;29    }30 31    private Trie searchPrefix(String s) {32        Trie node = this;33        for (char c : s.toCharArray()) {34            int idx = c - 'a';35            if (node.children[idx] == null) {36                return null;37            }38            node = node.children[idx];39        }40        return node;41    }42}43 44/**45 * Your Trie object will be instantiated and called as such:46 * Trie obj = new Trie();47 * obj.insert(word);48 * boolean param_2 = obj.search(word);49 * boolean param_3 = obj.startsWith(prefix);50 */
交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。
动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。
适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。
AlgoViz Lab

实现 Trie (前缀树) · 解法对比

AlgoViz Lab

实现 Trie 的插入、完整词搜索和前缀搜索。

测试用例
insert apple; search apple; startsWith app
题目分类
字典树
解法对比
2
方案 1

字符串集合扫描前缀

完整词放 Set；前缀查询扫描所有词。

时间
startsWith O(NL)
空间
O(总字符)
方案 2

前缀树节点

每个字符是一条边，节点标记是否为完整词结尾。

时间
每次 O(L)
空间
O(总字符)