Overview

Design a data structure that supports adding new words and searching for words with wildcard support.

Your solution will be tested by processing a list of operations. Implement processWordFinder(operations) where each operation is:

• ["addWord", word] — adds word to the data structure.
• ["search", pattern] — returns true if any previously added word matches the pattern. A . in the pattern matches any single letter.

Return an array of results (null for addWord, boolean for search).

Constraints

• 1 ≤ word.length ≤ 25
• word in addWord consists only of lowercase English letters.
• pattern in search consists of lowercase English letters and . (dot).
• At most 10,000 calls total.

Examples

processWordFinder([
  ["addWord", "bad"],
  ["addWord", "dad"],
  ["addWord", "mad"],
  ["search", "pad"],    // → false
  ["search", "bad"],    // → true
  ["search", ".ad"],    // → true  — matches bad, dad, mad
  ["search", "b.."],    // → true  — matches bad
]);
// → [null, null, null, false, true, true, true]

Notes

• Use a Trie for storage. For search, when encountering a ., branch to all children and continue recursively.
• Exact characters follow the normal trie path.
• This is a DFS/backtracking search over the trie.

Solution

function processWordFinder(operations) {
  const root = {};
  const results = [];

  function addWord(word) {
    let node = root;
    for (const ch of word) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.$ = true;
  }

  function searchNode(word, idx, node) {
    if (idx === word.length) return node.$ === true;
    const ch = word[idx];
    if (ch === '.') {
      for (const key of Object.keys(node)) {
        if (key !== '$' && searchNode(word, idx + 1, node[key])) return true;
      }
      return false;
    }
    if (!node[ch]) return false;
    return searchNode(word, idx + 1, node[ch]);
  }

  for (const op of operations) {
    if (op[0] === "addWord") {
      addWord(op[1]);
      results.push(null);
    } else {
      results.push(searchNode(op[1], 0, root));
    }
  }

  return results;
}

Resources

• Design Add and Search Words — LeetCode
• Trie — Wikipedia