Skip to content

Instantly share code, notes, and snippets.

@Agnishom

Agnishom/trie.cpp

Created Apr 29, 2016
Embed
What would you like to do?
Tries
#include <iostream>
#include <string>
struct TrieNode{
int partial = 0;
TrieNode* next[26] = {nullptr};
};
class Contacts{
TrieNode root;
void insertR(std::string name, TrieNode node){
if (name.length() == 0)
return;
node.partial++;
char c = name[0];
if (node.next[c-'a'] == nullptr)
node.next[c-'a'] = new TrieNode;
std::cout << c << " " << (node.next[c-'a']==nullptr) ? 1 : 0) << " " << node.partial << std::endl;
insertR(name.substr(1),*node.next[c-'a']);
}
int findR(std::string name, TrieNode node){
if (name.length() == 0)
return node.partial;
char c = name[0];
std::cout << c << " " << ((node.next[c-'a']==nullptr) ? 1 : 0) << std::endl;
if (node.next[c-'a'] == nullptr)
return 0;
return findR(name.substr(1),*node.next[c-'a']);
}
public:
void insert(std::string name){
insertR(name,this->root);
}
int find (std::string name){
return findR(name,this->root);
}
};
int main(){
Contacts book;
//for testing
book.insert("hack");
book.insert("hackerrank");
std::cout << book.find("hac") << std::endl;
std::cout << book.find("hak") << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.