题目链接
LeetCode 208. 实现 Trie (前缀树)[1]
题目描述
实现一个 Trie （前缀树），包含 insert, search, 和 startsWith 这三个操作。
示例1
Trietrie=newTrie(); trie.insert("apple");trie.search("apple"); //返回truetrie.search("app"); //返回falsetrie.startsWith("app"); //返回truetrie.insert("app"); trie.search("app"); //返回true
说明：
题解
字典树主要支持插入字符串、查询字符串是否在字典树中、查询字典树中是否存在某个前缀等操作，我这里还额外实现了一下 c++ 版本的删除字符串操作。
初始化字典树
初始化的时候，根结点为空，不用来放任何字符，所有字符串都是从下一层子结点开始存储。
每个结点有 26 个指针，指向下一层子结点，每个指针代表着下一个不同的字母。
每个结点还保存了一个变量 isEnd ，用来表示该结点是不是某个字符串结束的位置。
插入字符串
从根结点往下递归，如果字符串中下一个字母对应的子结点为空，那就新建一个结点再递归，否则的话就直接递归下去。
最后把最后一个结点的 isEnd 设置为 1，表示这个结点是字符串的结束位置。
查询字符串
从根结点往下递归查找，如果字符串还没遍历结束，但是结点已经空了，说明字符串不在字典树中。否则的话一直查找到最后一个字符，然后看对应结点的 isEnd 是 1 还是 0，如果是 1 ，就存在字符串，否则不存在。
查询字符串前缀
和查询字符串过程一模一样，唯一的区别就是最后不用看最后一个结点的 isEnd 了，直接返回 true 。因为既然都查询到了最后一个字符了，说明这个前缀一定存在。
删除字符串
这个是我自己实现的，一般来说字典树很少用到删除操作。
首先整体框架是和查询字符串类似的，从根结点往下递归查询，然后用一个栈保存查询到的结点。
如果查询过程中直接遇到了空结点，就直接返回，因为都不存在字符串，就不用删除了。然后判断最后一个结点的类型。
如果它的 isEnd 是 0，说明字符串不存在，那就直接返回不用删了。
如果它不是叶子结点，说明后面还接着字符串呢，那也不用删了，只要把该结点的 isEnd 设置为 0 就行了。
否则的话它就是叶子结点，那么就直接删除这个结点，并且从栈里出栈。
然后从栈里最后一个结点开始删除，直到栈顶的结点不是叶子结点（表示字典树中存在删除字符串的相同前缀字符串）或者 isEnd 是 1（表示字典树中存在删除字符串的前缀子串）。
代码
具体实现上面，c++ 我采用的结构体指针来构建出了一颗树。而 python 我直接用的嵌套的字典，并没有真正的构建出树，只有一个类，这样还挺方便的，但是删除操作有点麻烦，暂时就不写了。
c++
classTrie { public: boolisEnd; vector<Trie*>next; Trie() { isEnd=false; next=vector<Trie*>(26, 0); } ~Trie() { for (autop : next) deletep; } voidinsert(stringword) { Trie*node=this; for (autoc : word) { if (node->next[c-'a'] ==NULL) { node->next[c-'a'] =newTrie(); } node=node->next[c-'a']; } node->isEnd=true; } voiddel(stringword) { stack<Trie*>st; Trie*node=this; for (autoc : word) { node=node->next[c-'a']; st.push(node); if (node==NULL) return; } if (!(node->isEnd)) return; if (!isLeaf(node)) { node->isEnd=false; return; } deletenode; st.pop(); while (!st.empty()) { node=st.top(); st.pop(); if (isLeaf(node) &&!(node->isEnd)) deletenode; elsebreak; } } boolsearch(stringword) { Trie*node=this; for (autoc : word) { node=node->next[c-'a']; if (node==NULL) returnfalse; } returnnode->isEnd; } boolstartsWith(stringprefix) { Trie*node=this; for (autoc : prefix) { node=node->next[c-'a']; if (node==NULL) returnfalse; } returntrue; } boolisLeaf(Trie*node) { for (autop : next) { if (p) returnfalse; } returntrue; } };
python
classTrie: def__init__(self): self.nxt= {} definsert(self, word: str) ->None: node=self.nxtforcinword: ifcnotinnode: node[c] = {} node=node[c] node['#'] =Truedefsearch(self, word: str) ->bool: node=self.nxtforcinword: ifcnotinnode: returnFalsenode=node[c] return'#'innodedefstartsWith(self, prefix: str) ->bool: node=self.nxtforcinprefix: ifcnotinnode: returnFalsenode=node[c] returnTrue
参考资料
[1]
LeetCode 208. 实现 Trie (前缀树): https://leetcode-cn.com/problems/implement-trie-prefix-tree/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
