SHARE
TWEET

Untitled

a guest Aug 24th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Initialize your data structure here.
  3.  */
  4. /*
  5. STEPS/PSEUDOCODE:
  6. 1. Create definition of an instance of Trie
  7. 2. example: {str: "", next: {another instance of Trie}}
  8. 3. Using binary tree
  9. */
  10. var Trie = function(text) {
  11.   var trie = {};
  12.   trie.str = text;
  13.   trie.left = null;
  14.   trie.right = null;
  15.   return trie;
  16. };
  17.  
  18. /**
  19.  * Inserts a word into the trie.
  20.  * @param {string} word
  21.  * @return {void}
  22.  */
  23. Trie.prototype.insert = function(word) {
  24.   //If word is greater than the last node then insert on leaf node
  25.   //Else insert on left side of lead node
  26.   //Setup base case which is where node.next === null
  27.   //Traverse binary search tree
  28.   if(this.trie === null) {
  29.     this.trie = new Trie(word);
  30.   }
  31.   var traverse = function(trie){
  32.     if(word < trie.str) {
  33.       if(trie.left === null){
  34.         trie.left = new Trie(word)
  35.         return;
  36.       }
  37.       else {
  38.         this.traverse(trie.left);
  39.       }
  40.     }
  41.     else {
  42.       //word >= trie.str
  43.       if(trie.right === null) {
  44.         trie.right = new Trie(word);
  45.         return;
  46.       }
  47.       else {
  48.         this.traverse(trie.right);
  49.       }      
  50.     }
  51.   }
  52.   traverse(this.trie);
  53. };
  54.  
  55. /**
  56.  * Returns if the word is in the trie.
  57.  * @param {string} word
  58.  * @return {boolean}
  59.  */
  60. Trie.prototype.search = function(word) {
  61.   var isFound = false;
  62.   var traverse = function(trie) {
  63.     if(trie.str === word){
  64.       isFound = true;
  65.       return isFound;
  66.     }
  67.     else if(word < trie.str){
  68.       traverse(trie.left);
  69.     }
  70.     else {
  71.       traverse(trie.right);
  72.     }
  73.   }
  74.   return traverse(this.trie);
  75. };
  76.  
  77. /**
  78.  * Returns if there is any word in the trie that starts with the given prefix.
  79.  * @param {string} prefix
  80.  * @return {boolean}
  81.  */
  82. Trie.prototype.startsWith = function(prefix) {
  83.   /*'string'.includes('sea',0);*/
  84.   var isFound = false;
  85.   var traverse = function(trie) {
  86.     if(trie.str.includes(prefix,0)){
  87.       isFound = true;
  88.       return isFound;
  89.     }
  90.     else if(word < trie.str){
  91.       traverse(trie.left);
  92.     }
  93.     else {
  94.       traverse(trie.right);
  95.     }
  96.   }
  97.   return traverse(this.trie);
  98. };
  99.  
  100. /**
  101.  * Your Trie object will be instantiated and called as such:
  102.  * var obj = new Trie()
  103.  * obj.insert(word)
  104.  * var param_2 = obj.search(word)
  105.  * var param_3 = obj.startsWith(prefix)
  106.  */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top