Trie

[hon9g]

Problems selected by LeetCode for the topic Trie 🌐

Click ✔️ to go to each solution. The Link to each problem🌐 is at the top of each solution.

🔗 Basic Operations

#	title	my solution
208	Implement Trie (Prefix Tree)	✔️

🔗 Practical Application I

#	title	my solution
677	Map Sum Pairs	✔️
648	Replace Words	✔️
642	Design Search Autocomplete System
211	Add and Search Word - Data structure design

🔗 Practical Application II

#	title	my solution
421	Maximum XOR of Two Numbers in an Array
212	Word Search II
425	Word Squares
336	Palindrome Pairs

[hon9g]

208. Implement Trie (Prefix Tree)

• 🌐problem

  Children in hash

• Time Complexity:
  • O(S) for insert
  • O(S) for search and prefix in average
• Space Complexity:
  • *O(26H) = O(H)**
  • H = the height of the tree = max length of the inputs

    
    /**

  • Node */ const Node = function(x) { this.val = x; this.childrens = new Map(); }

/**

• Trie */ var Trie = function() { this.root = new Node(null); };

/**

• Inserts a word into the trie.
• @param {string} word
• @return {void} */ Trie.prototype.insert = function(word) { let curr = this.root; for (c of word) { if (!curr.childrens.get(c)) { curr.childrens.set(c, new Node(c)); } curr = curr.childrens.get(c); } curr.childrens.set('.', new Node('.')); };

/**

• Returns if the word is in the trie.
• @param {string} word
• @return {boolean} */ Trie.prototype.search = function(word) { let curr = this.root; for (c of word) { const next = curr.childrens.get(c); if (!next) return false; curr = next } return curr.childrens.get('.') ? true : false; };

/**

• Returns if there is any word in the trie that starts with the given prefix.
• @param {string} prefix
• @return {boolean} */ Trie.prototype.startsWith = function(prefix) { let curr = this.root; for (c of prefix) { const next = curr.childrens.get(c); if (!next) return false; curr = next } return true; };

  
  ### Childrens in Array
  - Time Complexity:
  - **O(S)** for `insert`
  - **O(S)** for `search` and `prefix`
  - Space Complexity:
  - **O(26*H)** = **O(H)**
  - `H = the height of the tree = max length of the inputs`

[hon9g]

677. Map Sum Pairs

• 🌐problem

• Time Complexity: O(K) for insert and sum, K = length of the key
• Space Complexity: O(N) N = size of total inputs

  
  /** 
  * @param {string} key 
  * @param {number} val
  * @return {void}
  */
  const Node = function(val) {
  this.val = val;
  this.children = new Map();
  }

/**

• @return {void} */ var MapSum = function() { this.root = new Node(0); }; /**
• @param {string} key
• @param {number} val
• @return {void} */ MapSum.prototype.insert = function(key, val) { let curr = this.root; for (c of key) { if (!curr.children.has(c)) { curr.children.set(c, new Node(val)); } else { curr.children.get(c).val += val; } curr = curr.children.get(c); } if (curr.children.has('.')) { const oldVal = curr.children.get('.').val; curr = this.root; for (c of key) { curr.children.get(c).val -= oldVal; curr = curr.children.get(c); } } curr.children.set('.', new Node(val)); }; /**
• @param {string} prefix
• @return {number} */ MapSum.prototype.sum = function(prefix) { let curr = this.root; for (c of prefix) { if (!curr.children.has(c)) { return 0; } curr = curr.children.get(c); } return curr.val; };

[hon9g]

648. Replace Words

• 🌐problem

• D = length of dict * size of each word
• S = length of sentence * the size of each sentence
• Time Complexity: O(D+S)
• Space Complexity: O(D)

  const Node = function(x) {
  this.val = x;
  this.children = new Map();
  }
  /**
  * @param {string[]} dict
  * @param {string} sentence
  * @return {string}
  */
  var replaceWords = function(dict, sentence) {
  const res = [], head = new Node('');
  for (word of dict) {
      let curr = head;
      for (c of word) {
          if (!curr.children.has(c)) {
              curr.children.set(c, new Node(c));
          }
          curr = curr.children.get(c);
      }
      curr.children.set('.', new Node('.'));
  }
  for (word of sentence.split(' ')) {
      let curr = head, newWord = [];
      for (c of word) {
          if (!curr.children.has(c)) break;
          if (curr.children.has('.')) break;
          newWord.push(c);
          curr = curr.children.get(c);
      }
      if (newWord.length) {
          res.push(curr.children.has('.') ? newWord.join('') : word);
      } else {
          res.push(word);
      }
  }
  return res.join(' ');
  };

[hon9g]

642. Design Search Autocomplete System

• 🌐problem

  complexity analysis

• Time Complexity:
• Space Complexity:

[hon9g]

211. Add and Search Word - Data structure design

• 🌐problem

  complexity analysis

• Time Complexity:
• Space Complexity:

[hon9g]

421. Maximum XOR of Two Numbers in an Array

• 🌐problem

  complexity analysis

• Time Complexity:
• Space Complexity:

[hon9g]

212. Word Search II

• 🌐problem

  complexity analysis

• Time Complexity:
• Space Complexity:

[hon9g]

425. Word Squares

• 🌐problem

  complexity analysis

• Time Complexity:
• Space Complexity:

[hon9g]

336. Palindrome Pairs

• 🌐problem

  complexity analysis

• Time Complexity:
• Space Complexity: