Tries.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8907fcdc",
   "metadata": {},
   "source": [
    "# Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00833ba5",
   "metadata": {},
   "source": [
    "## Implement Trie\n",
    "\n",
    "* https://leetcode.com/problems/implement-trie-prefix-tree/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - insert: O(n), where n = length of the word\n",
    "        * reason being, looking up if the current node already has a child is O(1)\n",
    "        * and you need to iterate through all the letters in the word in order to insert them all\n",
    "        * for example, even if the word is already present in the Trie, you'll still have to iterate through the entire word to make sure\n",
    "    - search: O(n)\n",
    "        * also O(n) for the same reason above\n",
    "        * the last check to see if node.end = true is O(1)\n",
    "    - startsWith: O(n), where n = length of the prefix\n",
    "        * same reason above\n",
    "* Space Complexity:\n",
    "    - insert: O(n)\n",
    "        * best case scenario, you don't need to create any new nodes\n",
    "        * worst case scenario, you create new nodes for every letter in the word\n",
    "        * on average, you'll probably only have to make a couple of new nodes\n",
    "    - search: O(1)\n",
    "        * you don't create new nodes to search\n",
    "    - startsWith: O(1)\n",
    "        * same reason as above\n",
    "***\n",
    "* empty root node that you can attach the first letter of any words inserted into\n",
    "    - root node will have at most 26 nodes, 1 for each letter of the alphabet\n",
    "* each node will have a children and a end property\n",
    "    - children = {}, where key = 'letter' and value = another node\n",
    "    - end = boolean, will tell you if this is the last letter of a word you inserted\n",
    "        * so if you inserted apple and app, 'e' would be the end for 'apple' and 'p' would be the end for 'app'\n",
    "* think of it like a linked list for all operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3522d7fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "var TrieNode = class {\n",
    "    constructor() {\n",
    "        this.children = {};\n",
    "        this.end = false;\n",
    "    }\n",
    "}\n",
    "\n",
    "var Trie = function() {\n",
    "    // null node to add all the letters to\n",
    "    // it'll have at most 26 nodes attached to it\n",
    "    // 1 for each letter of the alphabet\n",
    "    this.root = new TrieNode();\n",
    "};\n",
    "\n",
    "/** \n",
    " * @param {string} word\n",
    " * @return {void}\n",
    " */\n",
    "Trie.prototype.insert = function(word) {\n",
    "    let current = this.root;\n",
    "    \n",
    "    for (let i = 0; i < word.length; i++) {\n",
    "        let letter = word[i];\n",
    "        // if letter is not present\n",
    "        if (current.children[letter] === undefined) {\n",
    "            current.children[letter] = new TrieNode();\n",
    "        }\n",
    "        current = current.children[letter];\n",
    "    }\n",
    "    \n",
    "    current.end = true;\n",
    "};\n",
    "\n",
    "/** \n",
    " * @param {string} word\n",
    " * @return {boolean}\n",
    " */\n",
    "Trie.prototype.search = function(word) {\n",
    "    let current = this.root;\n",
    "    let i = 0;\n",
    "    \n",
    "    while (current !== undefined && i < word.length) {\n",
    "        current = current.children[word[i]];\n",
    "        i++;\n",
    "    }\n",
    "    \n",
    "    return current !== undefined ? current.end : false;\n",
    "};\n",
    "\n",
    "/** \n",
    " * @param {string} prefix\n",
    " * @return {boolean}\n",
    " */\n",
    "Trie.prototype.startsWith = function(prefix) {\n",
    "    let current = this.root;\n",
    "    let i = 0;\n",
    "    \n",
    "    while (current !== undefined && i < prefix.length) {\n",
    "        current = current.children[prefix[i]];\n",
    "        i++;\n",
    "    }\n",
    "    \n",
    "    return current !== undefined;\n",
    "};\n",
    "\n",
    "/** \n",
    " * Your Trie object will be instantiated and called as such:\n",
    " * var obj = new Trie()\n",
    " * obj.insert(word)\n",
    " * var param_2 = obj.search(word)\n",
    " * var param_3 = obj.startsWith(prefix)\n",
    " */"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "728fe3e8",
   "metadata": {},
   "source": [
    "## Design Add and Search Words Data Structure\n",
    "\n",
    "* https://leetcode.com/problems/design-add-and-search-words-data-structure/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - addWord(word): O(n)\n",
    "        * either have to traverse or create a trie node to add to the Trie and you have to do this for every character in the word\n",
    "        * the last operation to set the node.ends flag to true is O(1)\n",
    "    - search(word): O(V + E) \n",
    "        * V = number of nodes in the Trie \n",
    "        * E = number of edges between nodes in the Trie\n",
    "        * reason being, we are essentially doing DFS (depth first search) on the Trie if there is a \\* in the word, e.g. b\\*d\n",
    "* Space Complexity:\n",
    "    - addWord(word): O(n)\n",
    "        * have to create Trie nodes and add them to the Trie\n",
    "    - search(word): O(h)\n",
    "        * we do use recursion for this so we implicitly use a stack but the dominant term is definitely the length of the Trie\n",
    "        * if we have a bunch of \\*, then we have to go deeper down the Trie then come back up\n",
    "***\n",
    "* search for the word normally if we do not encounter any \\* in the word\n",
    "* use dfs when we encounter one\n",
    "    - reason being, we have to go deeply down the branches of a Trie to find our word\n",
    "    - then if the last node ends (node.ends === true), then we can return true\n",
    "    - else we have to backtrack and search down other branches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "eeb02a05",
   "metadata": {},
   "outputs": [],
   "source": [
    "/** \n",
    " * Your WordDictionary object will be instantiated and called as such:\n",
    " * var obj = new WordDictionary()\n",
    " * obj.addWord(word)\n",
    " * var param_2 = obj.search(word)\n",
    " */\n",
    "\n",
    "var TrieNode = class {\n",
    "    constructor() {\n",
    "        this.children = {};\n",
    "        this.ends = false;\n",
    "    }\n",
    "}\n",
    "\n",
    " var WordDictionary = class {\n",
    "     constructor() {\n",
    "         this.head = new TrieNode();\n",
    "     }\n",
    "\n",
    "     addWord(word) {\n",
    "         let current = this.head;\n",
    "         for (let i = 0; i < word.length; i++) {\n",
    "             let letter = word[i];\n",
    "             if (current.children[letter] === undefined) {\n",
    "                 current.children[letter] = new TrieNode();\n",
    "             }\n",
    "             \n",
    "             current = current.children[letter];\n",
    "         }\n",
    "         current.ends = true;\n",
    "     }\n",
    "\n",
    "     search(word) {\n",
    "         let isFound = false;\n",
    "\n",
    "         const dfs = (node, i) => {\n",
    "             if (!isFound) {\n",
    "                 if (i === word.length && node.ends) {\n",
    "                     isFound = true;\n",
    "                     return;\n",
    "                 }\n",
    "\n",
    "                 let letter = word[i];\n",
    "                 if (letter === \".\") {\n",
    "                     // call dfs for each child of the current node\n",
    "                     for (let child in node.children) {\n",
    "                         dfs(node.children[child], i + 1);\n",
    "                     }\n",
    "                 }\n",
    "                 else if (node.children[letter] !== undefined) {\n",
    "                     dfs(node.children[letter], i + 1);\n",
    "                 }\n",
    "\n",
    "                 return;\n",
    "             }\n",
    "         }\n",
    "\n",
    "\n",
    "         dfs(this.head, 0);\n",
    "\n",
    "         return isFound;\n",
    "     }\n",
    " }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a4e9cfe",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb79c8aa",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f899be36",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e490be88",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "JavaScript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "16.14.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}