当前位置：首页 > news >正文

054实现Trie(前缀树)

news 2026/8/10 23:05:12

实现Trie(前缀树)

题目链接：https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

无

分析：一开始想到用二维数组记录在每个长度上每个字母出现的次数，并用另一个二维数组记录在某个长度以某个字母结尾的单词的个数，但后面通过自己列举样例发现此方法行不通，例如：当插入“applea”、"abbbe"后，查询字符串"apple"是否在字符串中，此时前缀树既存在 “apple” 路径，又存在长度5上以"e"结尾的单词，按照我的设计此时应该返回true，但是"apple"并不存在于前缀树中，故此方法行不通。

看了官方题解后的解答：

private Trie[] children; private boolean isEnd;//标识是否为尾节点 public Trie() { children = new Trie[26]; } public void insert(String word) { Trie cur = this; for(int i=0; i<word.length(); i++){ char ch = word.charAt(i); int index = ch - 'a'; if(cur.children[index] == null){ cur.children[index] = new Trie(); } cur = cur.children[index]; } cur.isEnd = true; } public boolean search(String word) { Trie end = searchPrefix(word); return end != null && end.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } private Trie searchPrefix(String prefix){ Trie cur = this; for(int i=0; i<prefix.length(); i++){ char ch = prefix.charAt(i); int index = ch - 'a'; if(cur.children[index] == null){ return null; } cur = cur.children[index]; } return cur; }

分析：

1、代码的时间复杂度：初始化为 O(1)，其余操作为 O(∣S∣)，其中 ∣S∣ 是每次插入或查询的字符串的长度。

2、代码的空间复杂度：O(∣T∣⋅Σ)，其中 ∣T∣ 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。

3、解题思路：采用字典树，Trie类相当于字典树的节点，字典树的每个节点包含26个指向子节点的指针（因为题中注明了测试样例只包含小写字母）和一个变量isEnd（用来标识当前节点是否为某个字符串的结尾）。知道了字典树的结构，那么题中要求实现的三个方法就很容易实现了。

4、我的解答思路偏离了题目意思，我想的是只用一个二维数组来维护所有，并没有把Trie类当作一个树的节点来看待，就会导致出现我列举的样例中的问题。但是题目其实已经告诉我们需要实现前缀树，那么自然而然地就应该想到Trie类是树的节点。