Lintcode442 Implement Trie solut
2018-03-04 本文已影响0人
程风破浪会有时
【题目描述】
Implement a trie with insert, search, and startsWith methods.
Notice
You may assume that all inputs are consist of lowercase letters a-z.
实现一个 Trie，包含 insert, search, 和 startsWith 这三个方法。
注意事项
你可以假设所有的输入都是小写字母a-z。
【题目链接】
www.lintcode.com/en/problem/implement-trie/
【题目解析】
本题考查字典树数据结构的基础知识。
我们将字母的字典树每个节点定义一个大小为26的子节点指针数组，然后用一个标志符用来记录到当前位置为止是否为一个词，初始化的时候讲26个子节点都赋为空。那么insert操作只需要对于要插入的字符串的每一个字符算出其的位置，然后找是否存在这个子节点，若不存在则新建一个，然后再查找下一个。查找词和找前缀操作跟insert操作都很类似，不同点在于若不存在子节点，则返回false。查找次最后还要看标识位，而找前缀直接返回true即可。
【参考答案】
