Tries : Contacts

try-tries.cpp

// c++ solution

#include <iostream>

using namespace std;

struct Node {
    int count;
    Node* next;
    
    Node() : count(0), next(nullptr) {};
    ~Node() {
        delete[] next;
    }
};

void add(string contact, Node* root) {
  Node* crawler = root;
  int len = contact.size();
  
  for (int i = 0; i < len; ++i) {
    char c = contact[i];
    int index = c - 'a';
    
    crawler[index].count++;
    
    if (i != len - 1) {
      if (crawler[index].next == nullptr) {
        crawler[index].next = new Node[26];
      }
      
      crawler = crawler[index].next;
    }
  }
}

int find(string contact, Node* root) {
    Node* crawler = root;
    int len = contact.size();
    int count; // circumvent compiler warning treated as error
    
    for (int i = 0; i < len; ++i) {
      char c = contact[i];
      int index = c - 'a';
      
      if (!crawler[index].count) {
        return 0;
      }
      if (i == len - 1) {
        count = crawler[index].count;
      }
      
      crawler = crawler[index].next;
    }
    
    // useless, but compiler treated a warning as an error
    return count;
}


int main(){
    int n;
    cin >> n;
    
    // make trie
    Node* root = new Node[26];
    
    for(int a0 = 0; a0 < n; a0++){
      string op;
      string contact;
      cin >> op >> contact;
      
      if (op == "add") {
        add(contact, root);
      } else {
        cout << find(contact, root) << endl;
      }
    }
    
    delete[] root;
}