Design Add and Search Words Data Structure

The following code uses “Trie” data structure. The character ‘.’ in a word could represent any letter when searching.

class TrieNode {
  constructor(val) {
    this.val = val;
    this.children = {};
    this.isWord = false;
  }
}

var WordDictionary = function() {
  this.root = new TrieNode(null);
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
  let current = this.root;
  const charArray = word.split('');
  for (const s of charArray) {
    if (!(s in current.children)) {
      current.children[s] = new TrieNode(s);
    }
    current = current.children[s];
  }
  current.isWord = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
  return this.searchString(word, this.root);
};

WordDictionary.prototype.searchString = function(str, node) {
  let current = node;
  const charArray = str.split('');
  for (const [index, char] of Object.entries(charArray)) {
    if (!(char in current.children)) {
      if (char === '.') {
        for (const [key, childNode] of Object.entries(current.children)) {
          if (this.searchString(str.substring(parseInt(index) + 1), childNode)) {
            return true;
          }
        }
      }
      return false;
    } else {
      current = current.children[char];
    }
  }
  return current.isWord;
};

var obj = new WordDictionary();
obj.addWord('bad');
obj.addWord('bat');
obj.addWord('cat');
console.log(obj.search('b..')); // true
console.log(obj.search('cat')); // true
console.log(obj.search('dog')); // false

Demo

Related