208. Implement Trie (prefix tree)

答 案 :

  1. Each node in the prefix tree is represented by an object.
  2. Each letter of a word is a nodekey, itsvalueIs an object.
  3. At the end of the word node, insertkeyandvalueforEOFMeans the word ends here.
  4. When an insert operation is performed, each letter is inserted as a node in the prefix tree in order.
  5. Search in the prefix tree in alphabetical order, encounteredEOFIndicates that the word is in the prefix tree.
/** * Initialize your data structure here. */
var Trie = function () {
  // The root node uses an empty object with each letter of the word as a key for the object
  this.root = {};
  // Use a fixed tag to mark a node as the root node of the prefix tree
  // Use Symbol to avoid duplication
  this.endOfWord = Symbol('EOF');
};

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}* /
Trie.prototype.insert = function (word) {
  // When a word is inserted into the prefix tree, it is inserted from the root node
  let node = this.root;

  // Walk through the word letter by letter
  for (const char of word) {
    // If the letter is not in the prefix tree, create a new node
    node[char] = node[char] || {};
    // Move the node down
    node = node[char];
  }

  // Mark the current node as the end of a word
  node[this.endOfWord] = this.endOfWord;
};

/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}* /
Trie.prototype.search = function (word) {
  // The search for a word starts at the root node
  let node = this.root;

  // Look for each letter of the word in the prefix tree
  for (const char of word) {
    // If the current letter does not exist in the prefix tree, the word must not exist either
    if(! node[char]) {return false;
    }

    // Move the node and look down
    node = node[char];
  }

  // If the node corresponding to the last letter of the word is marked as the end of the word in the prefix tree, the word exists in the prefix tree
  return node[this.endOfWord] === this.endOfWord;
};

/**
 * 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) {
  // Start from the root node to determine whether the word exists
  let node = this.root;

  // Look for each letter of the word in the prefix tree
  for (const char of prefix) {
    // If the current letter does not exist in the prefix tree, the word must not exist either
    if(! node[char]) {return false;
    }

    // Move the node and look down
    node = node[char];
  }

  // There is no need to determine whether the word exists in the prefix tree, as long as all letters of the word exist in the prefix tree
  return true;
};
Copy the code