/**
 * Initialize your data structure here.
 */
var TrieNode = function () {
  this.links = new Map();
}

var Trie = function () {
  this.root = new TrieNode();
  this.root.links.set(0, true);
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  var node = this.root;
  for (var w of word) {
    if (node.links.has(w)) {
      node = node.links.get(w);
    } else {
      node.links.set(w, new TrieNode());
      node = node.links.get(w);
    }
  }
  node.links.set(0, true);
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  var node = this.root;
  for (var w of word) {
    if (!node.links.has(w)) {
      return false;
    }
    node = node.links.get(w);
  }
  return node.links.has(0);
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  var node = this.root;
  for (var w of prefix) {
    if (!node.links.has(w)) {
      return false;
    }
    node = node.links.get(w);
  }
  return true;
};