Q38: Design Add and Search Words Data Structure

Design a data structure supporting adding words and searching words, where the '.' character can match any single letter.

Trie Wildcard Search Engine

class WordDictionary {
  constructor() {
    this.root = {};
  }

  addWord(word) {
    let node = this.root;
    for (let char of word) {
      if (!node[char]) node[char] = {};
      node = node[char];
    }
    node.isEnd = true;
  }

  search(word) {
    function dfs(node, i) {
      if (i === word.length) return !!node.isEnd;
      const char = word[i];
      
      if (char === '.') {
        for (let key in node) {
          if (key !== 'isEnd' && dfs(node[key], i + 1)) return true;
        }
        return false;
      }
      
      if (!node[char]) return false;
      return dfs(node[char], i + 1);
    }
    return dfs(this.root, 0);
  }
}

const wd = new WordDictionary();
wd.addWord('bad');
console.log(wd.search('.ad')); // true

💡 Extends basic Trie structure. If search character is ., loops through all child branches recursively; otherwise follows standard character branch.

Key Takeaways

Combines Trie storage with DFS recursion when encountering wildcard . characters.
Wildcard . branches out to search all available children nodes at current tree depth.

Knowledge Check

How does the search algorithm process a wildcard '.' character during DFS?

Q38: Design Add and Search Words Data Structure

STAY UPDATED WITH BYTES!