Tries

trie.cpp

#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;
}