Word Finder

Implement wordFinder() — a factory that returns a small data structure for storing words and looking them up, where a query may contain the wildcard character . that matches any single letter. It is the classic autocomplete / spell-check building block: you load a dictionary once, then run many membership queries against it, some of which have "holes" you want filled by any letter. This is not a grid or path problem — there is no board and no adjacency. You are designing the container and its two operations.

Signature

// wordFinder() returns an object with two methods:
interface WordFinder {
  // Insert a word into the structure. Words are non-empty, lowercase a–z.
  // The same word may be added more than once; that's a no-op.
  addWord(word: string): void;

  // Return true if some stored word matches `query` exactly (same length).
  // A '.' in `query` matches ANY single letter. Other chars match literally.
  search(query: string): boolean;
}

function wordFinder(): WordFinder;

Examples

const wf = wordFinder();
wf.addWord('bad');
wf.addWord('dad');
wf.addWord('mad');

wf.search('pad'); // → false  (no stored word "pad")
wf.search('bad'); // → true   (exact literal match)
wf.search('.ad'); // → true   ('.' matches b/d/m → "bad"/"dad"/"mad")
wf.search('b..'); // → true   ("bad")

// The match is length-exact: '.' is exactly one letter, never zero or many.
const wf = wordFinder();
wf.addWord('a');

wf.search('a');  // → true
wf.search('.');  // → true   (one wildcard, one stored letter)
wf.search('');   // → false  (no empty word was added)
wf.search('..'); // → false  ("a" has length 1, query has length 2)

Notes

• . matches exactly one letter — never zero, never a run. search('..') only matches stored words of length two. There is no *-style "any number of letters" wildcard here.
• Search is whole-word — search('ba') against a stored 'bad' is false. The query length must equal the matched word's length.
• A fresh structure is empty — search on anything before any addWord returns false, including search('').
• Inputs are lowercase a–z in addWord; queries are lowercase a–z plus .. You do not need to validate input, handle uppercase, or handle other punctuation.
• addWord is called many times, then search many times. Favour a structure that makes wildcard search fast over one that re-scans the whole dictionary per query — see the solution.
• Don't worry about deletion, prefix search (returning all words under a prefix), Unicode, or a * wildcard. Those are out of scope.