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 (yeniden ifade)

addWord(word) ve search(word) destekle; search herhangi harfle eşleşen ‘.’ içerebilir.

Sezgi

Standart trie insert. search’te ‘.’ DFS ile her çocuğa dallanır.

Yaklaşımlar

Trie + '.' için DFS

Doğrulanmadı

Zaman O(L) add, O(26^L) worst searchAlan O(total chars)

Fikir. dfs(i, node): kelime sonunda End bayrağını kontrol et; harf tek çocuğu izler; nokta tüm çocukları dener.

Yürüyüş. add “bad”,“dad”,“mad”; search “pad” false, “bad” true, “.ad” true, “b..” true.

Trade-off. Tüm kelimeler üzerinde regex daha basit ama çok add için daha yavaş.

Çözüm

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);
  }
}

Şablon bağlantısı

Joker dallanmalı Trie.

Yansıma

. her çocuğu dener. Düz harf tek çocuğa iner. İlk eşleşmede true.
a.c üç adım, ortası her harf. Boş trie’de arama false.
Nokta yoksa bu, düz trie aramasıdır. Geri dönüşte kardeş harfi denemek için DFS şart.