题目概览Trie发音类似 try或者说前缀树是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补全和拼写检查。请你实现 Trie 类Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中返回true即在检索之前已经插入否则返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix返回true否则返回false。示例输入[Trie, insert, search, search, startsWith, insert, search] [[], [apple], [apple], [app], [app], [app], [app]]输出[null, null, true, false, true, null, true]解释Trie trie new Trie(); trie.insert(apple); trie.search(apple); // 返回 True trie.search(app); // 返回 False trie.startsWith(app); // 返回 True trie.insert(app); trie.search(app); // 返回 True提示1 word.length, prefix.length 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数总计不超过3 * 104次来源208. 实现 Trie (前缀树) - 力扣LeetCode解题分析方法字典树定义一个字典树当前节点只存储首个字母该字母连接一个新节点存储下个字母以此类推。由于字母都是小写英文字母因此可以用 26 位数组存储每个字母后一个节点。search 或startsWith时遍历传入单词字母找到第一个字母对应的数组节点然后进入该节点继续找下个字母直到遍历完成。如果找不到就返回 false但由于无法知道后续是否还有节点因此需要定义一个变量 isEnd 来判断是否是单词结尾在 insert 时添加如果传入的字母找完了且isEnd 为 true 时search 返回 true如果是startsWith找完就返回true。时间复杂度O(1)空间复杂度O(nm) n 为字符串个数m为字符串长度class Trie { private Trie[] children; private boolean isEnd; public Trie() { children new Trie[26]; isEnd false; } public void insert(String word) { Trie node this; for(int i 0; i word.length(); i) { char c word.charAt(i); if (node.children[c - a] null) { node.children[c - a] new Trie(); } node node.children[c - a]; } node.isEnd true; } public boolean search(String word) { Trie node findEndNode(word); return node ! null node.isEnd; } public boolean startsWith(String prefix) { Trie node findEndNode(prefix); return node ! null; } private Trie findEndNode(String str) { Trie node this; for (int i 0; i str.length(); i) { char c str.charAt(i); if (node.children[c - a] null) { return null; } node node.children[c - a]; } return node; } } /** * Your Trie object will be instantiated and called as such: * Trie obj new Trie(); * obj.insert(word); * boolean param_2 obj.search(word); * boolean param_3 obj.startsWith(prefix); */