Implement Trie (Prefix Tree)

<aside> 💡 Every new letter creates nesting inside previous letter.

const trie = {
  root: {
    h: {
      e: {
        l: {
          l: {
            o: {
              isWord: true
            }
          },
          i: {
            u: {
              m: {
                isWord: true
              }
            }
          }
        }
      }
    }
  }
};

</aside>

https://leetcode.com/problems/implement-trie-prefix-tree/

function Trie() {
  this.root = {};
}

Trie.prototype.insert = function (word) {
  // initialize pointer
  let current = this.root;

  for (const letter of word) {
    // create new level
    if (!current[letter]) {
      current[letter] = {};
    }
    // just move pointer if there is a letter already
    current = current[letter];
  }

  // mark as end
  current.end = true;
};

Trie.prototype.search = function (word) {
  let currentRoot = this.root;

  for (let i = 0; i < word.length; i++) {
    const letter = word[i];

    currentRoot = currentRoot[letter];

    if (!currentRoot) {
      return false;
    }
  }

  // check if it's an end
  return currentRoot.end ? true : false;
};

Trie.prototype.startsWith = function (word) {
  let current = this.root;

  for (const letter of word) {
    current = current[letter];
    if (!current) {
      return false;
    }
  }

  return true;
};

<aside> 💡

</aside>

• Solution