Implement a trie with
insert
, search
, and startsWith
methods.
Example:
Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true
Note:
- You may assume that all inputs are consist of lowercase letters
a-z
. - All inputs are guaranteed to be non-empty strings.
A:
不要搞得太复杂,就是每个character一个节点就行了了。(外加HashMap)( empty String “” 是所有 字符串的前缀。~~~即使还没有开始存)
class Trie { public: /** Initialize your data structure here. */ Trie() { root = new Node(); } /** Inserts a word into the trie. */ void insert(string word) { Node *cur = root; for(int i =0;i<word.length();++i) { char ch = word[i]; if(cur->chmap.find(ch) == cur->chmap.end()) { Node* tmp = new Node(); cur->chmap[ch] = tmp; } cur = cur->chmap.at(ch); } cur->isLeaf = true; } /** Returns if the word is in the trie. */ bool search(string word) { Node *cur = root; for(int i =0;i<word.length();++i) { char ch = word[i]; if(cur->chmap.find(ch)==cur->chmap.end()) { return false; } cur = cur->chmap.find(ch)->second; } return cur->isLeaf; } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { Node *cur = root; for(int i =0;i<prefix.length();++i) { char ch = prefix[i]; if(cur->chmap.find(ch)==cur->chmap.end()) { return false; } cur = cur->chmap.find(ch)->second; } return true; } private: struct Node{ unordered_map<char,Node*> chmap; bool isLeaf=false; }; Node * root; // root contains no char to reach it }; /** * 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); */
Mistakes:
1: 一开始加上了,如果该节点后面没有,就自己保存一个string,搞得太复杂
2: 这道题,最容易错的地方是,search和 startWith中,最后要检查是否是null节点。
No comments:
Post a Comment