One Pager Cheat Sheet

• You should implement a Trie data structure with add, search, and remove methods that have O(n) time complexity & O(26 * n * N) space complexity, where n is the length of the word and N is the total number of strings.
• We need to be familiar with Tries, which can be represented by a tree structure like * / \ c a / \ o end / \ t r / \ end end end.
• Using add, search and remove, we can construct and utilize a class structure to create and traverse a tree structure, with a head node that branches off to each character value, and leaves to indicate the end of a word.
• Create references to the head node, then process each letter of the word (e.g. "cat") and add them as children or grandchildren, either adding a new key or marking the existing leaf node, depending on if the key is present or not.
• We can use a while loop to determine the appropriate place to assign our word as a child key in a children hash, searching for each of its characters and handling the lineages created by previously added words.
• Let's pause to ensure we've properly understood the situation, to avoid adding a new branch of c -> a when we already have c -> a -> t, c -> a -> b, etc.
• We can use a while loop to iterate through each letter of the word and create nodes and attach them to the appropriate key in both JS and Python.
• We can traverse from node to node to search for words by comparing our currentChar to the children's keys, and optionally returning the depth or the word itself once the end of the word is reached.
• We can search and remove words from the trie in O(n) time using removeHelper and _empty functions.
• We can recursively call a removeHelper method to delete any child nodes found.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

class Trie {

  constructor() {

    this.head = {

      val: '',

      children: {},

    };

  }

​

  add(val) {

    let currentNode = this.head,

      newNode = null,

      currentChar = val.slice(0, 1);

​

    val = val.slice(1);

​

    // See how deep we can get in any existing branches

    while (

      typeof currentNode.children[currentChar] !== 'undefined' &&

      currentChar.length > 0

    ) {

      currentNode = currentNode.children[currentChar];

      currentChar = val.slice(0, 1);

      val = val.slice(1);

    }

​

    // Break each character into levels respectively

    // 'val' is the character, and 'value' lets us know if it terminates

    while (currentChar.length) {

      newNode = {

        val: currentChar,

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.