OJ Board

Code: Select all

#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;

string word;

struct trie {
  map<char,trie *> m;
  bool isend;
  trie() {
    isend=false;
  }
};

void insert(trie *&root, int pos) {
  if(word[pos]=='\0') {
    root->isend=true;
    return;
  }
  if(root->m.find(word[pos])==root->m.end())
    root->m[word[pos]]=new trie();
  insert(root->m[word[pos]], pos+1);
}

void del(trie *root) {
  for(map<char,trie *>::iterator it=root->m.begin();it!=root->m.end();it++)
    del(it->second);
  delete root;
}

int find(trie *root, int pos) {
  if(word[pos]=='\0')
    return root->isend;
  if(root->m.find(word[pos])==root->m.end())
    return 0;
  return find(root->m[word[pos]], pos+1);
}

int main() {
  trie *t=new trie();

  word="asdf";
  insert(t, 0);
  word="asdfjkl;";
  insert(t, 0);
  word="jkl;";
  insert(t, 0);

  word="asdf";
  cout << word << " found=" << find(t, 0) << endl;
  word="asdfj";
  cout << word << " found=" << find(t, 0) << endl;

  del(t);
  return 0;
}