实现Trie(前缀树)题目链接https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envTypestudy-plan-v2envIdtop-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 i0; iword.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 i0; iprefix.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类是树的节点。总结本题主要需要掌握字典树在本题中可以将字典树想象成一个26叉树了解了字典树的结构后方法实现上几乎没有难度。