Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtrie

Design Add and Search Words Data Structure

Problem (restated)

Support addWord(word) and search(word) where search may contain ‘.’ matching any letter.

Intuition

Standard trie insert. On search, ‘.’ branches to every child via DFS.

Approaches

Trie + DFS for '.'

Unverified

Time O(L) add, O(26^L) worst searchSpace O(total chars)

Idea. dfs(i, node): end of word checks End flag; letter follows one child; dot tries all children.

Walkthrough. add “bad”,“dad”,“mad”; search “pad” false, “bad” true, “.ad” true, “b..” true.

Trade-offs. Regex over all words is simpler but slower for many adds.

Solution

type Node = { children: Map<string, Node>; end: boolean };

export class WordDictionary {
  private root: Node = { children: new Map(), end: false };

  addWord(word: string): void {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, { children: new Map(), end: false });
      n = n.children.get(c)!;
    }
    n.end = true;
  }

  search(word: string): boolean {
    const dfs = (i: number, n: Node): boolean => {
      if (i === word.length) return n.end;
      const c = word[i]!;
      if (c === ".") {
        for (const child of n.children.values()) if (dfs(i + 1, child)) return true;
        return false;
      }
      const next = n.children.get(c);
      return !!next && dfs(i + 1, next);
    };
    return dfs(0, this.root);
  }
}

type Node = { children: Map<string, Node>; end: boolean };

export class WordDictionary {
  private root: Node = { children: new Map(), end: false };

  addWord(word: string): void {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, { children: new Map(), end: false });
      n = n.children.get(c)!;
    }
    n.end = true;
  }

  search(word: string): boolean {
    const dfs = (i: number, n: Node): boolean => {
      if (i === word.length) return n.end;
      const c = word[i]!;
      if (c === ".") {
        for (const child of n.children.values()) if (dfs(i + 1, child)) return true;
        return false;
      }
      const next = n.children.get(c);
      return !!next && dfs(i + 1, next);
    };
    return dfs(0, this.root);
  }
}

Template connection

Trie with wildcard branching.

Reflection

A . tries every child. A plain letter steps into one child. Return true on the first match.
a.c is three steps, and the middle step is every letter. A search on an empty trie is false.
With no dot this is an ordinary trie search. DFS is what lets a failed branch try the next letter.