Implement Trie
Implement a trie with insert, search, and startsWith methods.
http://www.lintcode.com/en/problem/implement-trie/
Solution
/**
* Your Trie object will be instantiated and called as such:
* Trie trie;
* trie.insert("lintcode");
* trie.search("lint"); will return false
* trie.startsWith("lint"); will return true
*/
class TrieNode {
public:
// Initialize your data structure here.
TrieNode() {
is_word = false;
}
bool is_word;
unordered_map<char, TrieNode*> neighbors;
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
void insert(string word) {
TrieNode *cur = root;
for(auto const& c : word) {
if(cur->neighbors.find(c) == cur->neighbors.end()) {
TrieNode *newnode = new TrieNode();
cur->neighbors[c] = newnode;
}
cur = cur->neighbors[c];
}
cur->is_word = true;
}
// Returns if the word is in the trie.
bool search(string word) {
TrieNode *cur = root;
//return searchDFS(word, 0, cur);
for(auto const& c : word) {
if(cur->neighbors.find(c) == cur->neighbors.end()) {
return false;
}
cur = cur->neighbors[c];
}
return cur->is_word;
//return false;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode *cur = root;
for(auto const& c : prefix) {
if(cur->neighbors.find(c) == cur->neighbors.end()) {
return false;
}
cur = cur->neighbors[c];
}
return true;
}
private:
TrieNode* root;
//也可以用递归实现search
bool searchDFS(string& word, int pos, TrieNode* cur) {
if(pos == word.length()) {
return cur->is_word;
}
if(cur->neighbors.find(word[pos]) == cur->neighbors.end())
return false;
return searchDFS(word, pos+1, cur->neighbors[word[pos]]);
}
};