【每日leetcode】实现Trie(前缀树）

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

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 说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。

c++代码

想偷个懒，结果超时了

class Trie { public: /** Initialize your data structure here. */ Trie() { } /** Inserts a word into the trie. */ void insert(string word) { trie.insert(word); } /** Returns if the word is in the trie. */ bool search(string word) { if(trie.find(word)!=trie.end()) return true; else return false; } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { for(auto tries:trie) { string tmp=tries.substr(0,prefix.length()); if(tmp.compare(prefix)==0) return true; else continue; } return false; } private: set<string> trie; }; /** * 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); */

那就老老实实实现trie树的结构吧

class Trie { public: /** Initialize your data structure here. */ Trie() { is_str=NULL; memset(next,0,sizeof(next)); } /** Inserts a word into the trie. */ void insert(string word) { Trie *cur=this;//根节点 for(char w:word){ if(cur->next[w-'a']==NULL)//下一个节点不存在 { Trie *newnode=new Trie();//新增一个节点 cur->next[w-'a']=newnode; } cur=cur->next[w-'a']; } cur->is_str=true; } /** Returns if the word is in the trie. */ bool search(string word) { Trie *cur=this; for(char w:word) { if(cur!=NULL) cur=cur->next[w-'a']; } return (cur!=NULL&&cur->is_str);//需要是一个完整的字符串 } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { Trie *cur=this; for(char w:prefix) { if(cur!=NULL) cur=cur->next[w-'a']; } return (cur!=NULL); } private: bool is_str;// Trie *next[26]; }; /** * 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); */