Implement Prefix Trie - HR Whiteboarding exercise

gistfile1.txt

// prefixTrie
// Insert, search, startsWith methods

/**
let trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true
*/

// Inputs: lowercase letters, always non-empty string
// Output: search - boolean; startsWith - boolean
// Edge cases: insert a word that's already in - would not insert twice
// Constraints: O(n) insert, O(n) best case search, O(n) startsWith

// apple, apply, apes, ape
// a
// p
// p  e  -  0,s
// l
// e  y
// 0  0

let endChar = '0';

/**
 * Trie - class implementation
 * @property {String} value: (character) = null
 * @property {Object} children
 */

/**
 * Insert a string into the prefix trie
 * @param {String} str
 */
// Attach endChar to end of input str
// Set current node to this node
// For each letter in string
  // If children contains letter
    // Set current node equal to child that contains letter
  // Else if children does not contain letter
    // Create a new node in current node's children 
    // Set current node equal to created node

/**
  Search - startsWith is similar
*/
// Attach endChar to input str
// set current node equal to root
// For each letter in input string
  // If endChar is current character, return true
  // If current node's children contains letter
    // Set current node equal to child that contained letter
  // Else return false