实现 Trie（前缀树）

图论

中等#208Java时间每个操作 O(L)，L 为字符串长度空间 O(所有插入单词的字符总数)

题目要做什么

实现前缀树，支持插入单词、精确搜索和前缀搜索。输入只含小写英文字母；精确搜索还要求终点被标记为完整单词。

题目示例输入

ops = ["Trie","insert","search","search","startsWith","insert","search"], args = [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]

题目示例输出[null,null,true,false,true,null,true]

01 为什么这样做

从根沿字符边前进，相同前缀共享同一路径。插入时补建缺失节点；单词终点用 end 标记，区分已有前缀与完整单词。

始终成立的条件

当前节点表示已经处理的字符前缀；end 只在完整插入单词的终点为真。

02 看见算法执行

动画与代码同步

修改输入，播放自己的例子

当前使用题目示例

演示输入 · JSON

预期输出 · 可选

修改输入会改变执行过程；预期输出用于核对结果。

数组 / nums步骤 1

执行状态

本次演示输出播放到最后查看

Solution.java参考解法

1class Trie {2    private final Trie[] children = new Trie[26];3    private boolean end;4    public Trie() { }5    public void insert(String word) {6        Trie node = this;7        for (int i = 0; i < word.length(); i++) {8            int index = word.charAt(i) - 'a';9            if (node.children[index] == null) node.children[index] = new Trie();10            node = node.children[index];11        }12        node.end = true;13    }14    public boolean search(String word) {15        Trie node = find(word);16        return node != null && node.end;17    }18    public boolean startsWith(String prefix) {19        return find(prefix) != null;20    }21    private Trie find(String word) {22        Trie node = this;23        for (int i = 0; i < word.length(); i++) {24            int index = word.charAt(i) - 'a';25            if (node.children[index] == null) return null;26            node = node.children[index];27        }28        return node;29    }30}

键盘控制：A 后退 · D 前进

实现 Trie（前缀树）

题目要做什么

这道题的完整课程将在正式实现中补齐

01 为什么这样做

02 看见算法执行

修改输入，播放自己的例子

编程练习

Java 编程练习