Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

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 '.'

Tested only

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?