Trie is a tree structure.
Usually, it is used to solve the dictionary problems.
Conditions:
1. dictionary problems ..
Mental cultivation:
1. A node with 26 children
2. find, insert, search …
Examples:
208 – Implement Trie (Prefix Tree)
648 – Replace Words
676 – Implement Magic Dictionary
677 – Map Sum Pairs
692 – Top K Frequent Words
720 – Longest Word in Dictionary
745 – Prefix and Suffix Search
211 – Design Add and Search Words Data Structure
Template:
#208, Implement Trie (Prefix Tree)
class Trie {
private:
struct TrieNode{
bool isWord;
vector<TrieNode*> children;
TrieNode(): isWord(false), children(26, nullptr){}
~TrieNode(){
for(TrieNode* child:children){
if(child) delete child;
}
}
};
unique_ptr<TrieNode> dummy;
TrieNode* find(string& source){
TrieNode* p = dummy.get();
for(char& s:source){
p = p->children[s - 'a'];
if(!p) break;
}
return p;
}
public:
/** Initialize your data structure here. */
Trie(): dummy(new TrieNode()) {
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode* head = dummy.get();
for(char& w: word){
if(!head->children[w - 'a']){
head->children[w - 'a'] = new TrieNode();
}
head = head->children[w - 'a'];
}
head->isWord = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode* head = find(word);
return head && head->isWord == true;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return find(prefix);
}
};
/**
* 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);
*/