实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个方法。
注意:
你可以假设所有的输入都是小写字母 a-z。
详见：https://leetcode.com/problems/implement-trie-prefix-tree/description/
Java实现：
Trie树，又称为字典树、单词查找树或者前缀树，是一种用于快速检索的多叉数结构。例如，英文字母的字典树是26叉数，数字的字典树是10叉树。
Trie树的基本性质有三点，归纳为：
根节点不包含字符，根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符串不相同。
insert：分析单词的每一个字符，如果存在与已经有的孩子中，则循环转到该孩子节点，否则新建孩子节点，最后在单词的末尾字符isWord标志位true；
search: 逐个分析每个字符，如果不存在该字符的孩子则返回false，否则循环之后，查看末尾字符的标志位即可；
prefix： 和search一样，只是在最后只要是都存在每个字符相应的孩子map，则返回true。
class TrieNode{
boolean isWord;
HashMap<Character,TrieNode> map;
public TrieNode(){
map=new HashMap<Character,TrieNode>();
}
}
class Trie {
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root=new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
char[] charArray=word.toCharArray();
TrieNode tmp=root;
for(int i=0;i<charArray.length;++i){
if(!tmp.map.containsKey(charArray[i])){
tmp.map.put(charArray[i],new TrieNode());//添加
}
tmp=tmp.map.get(charArray[i]);//转到孩子节点
if(i==charArray.length-1){//末尾字符
tmp.isWord=true;
}
}
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode tmp=root;
for(int i=0;i<word.length();++i){
TrieNode next=tmp.map.get(word.charAt(i));
if(next==null){
return false;
}
tmp=next;
}
return tmp.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode tmp=root;
for(int i=0;i<prefix.length();++i){
TrieNode next=tmp.map.get(prefix.charAt(i));
if(next==null){
return false;
}
tmp=next;
}
return true;
}
}
/**
* 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);
*/
C++实现：
class TrieNode
{
public:
TrieNode *next[26];
char c;
bool isWord;
TrieNode():isWord(false)
{
memset(next,0,sizeof(TrieNode*)*26);
}
TrieNode(char _c):c(_c),isWord(false)
{
memset(next,0,sizeof(TrieNode*)*26);
}
};
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
root=new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *p=root;
int id;
for(char c:word)
{
id=c-'a';
if(p->next[id]==nullptr)
{
p->next[id]=new TrieNode(c);
}
p=p->next[id];
}
p->isWord=true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode *p=root;
int id;
for(char c:word)
{
id=c-'a';
if(p->next[id]==nullptr)
{
return false;
}
p=p->next[id];
}
return p->isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode *p=root;
int id;
for(char c:prefix)
{
id=c-'a';
if(p->next[id]==nullptr)
{
return false;
}
p=p->next[id];
}
return true;
}
private:
TrieNode *root;
};
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* bool param_2 = obj.search(word);
* bool param_3 = obj.startsWith(prefix);
*/