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

Hardtrie

Word Search II

Problem (yeniden ifade)

Harf tahtası ve kelime listesi. Bir kelimede hücreyi yeniden kullanmadan bitişik (4-dir) hücrelerle oluşturulabilen tüm kelimeleri döndür.

Sezgi

Tüm kelimeleri trie’ye ekle. Her hücreden trie kenarlarını izleyerek DFS; End’de kelimeyi kaydet ve tekrarları önlemek için temizle; boş alt ağaçları buda.

Yaklaşımlar

Trie + tahta DFS budama

Doğrulanmadı

Zaman O(m·n·4·L)Alan O(Σ L)

Fikir. Hücreyi ‘#’ işaretle, 4 yöne özyinele, geri yükle. Keşiften sonra ölü trie düğümlerini sil.

Yürüyüş. Tahta o a a n / e t a e / i h k r / i f l v, kelimeler [“oath”,“pea”,“eat”,“rain”] → [“eat”,“oath”].

Trade-off. Kelime başına LC79 çok kelime için çok yavaş; paylaşılan önek trie kazanır.

Çözüm

type Node = { children: Map<string, Node>; word: string | null };

export function findWords(board: string[][], words: string[]): string[] {
  const root: Node = { children: new Map(), word: null };
  for (const w of words) {
    let n = root;
    for (const c of w) {
      if (!n.children.has(c)) n.children.set(c, { children: new Map(), word: null });
      n = n.children.get(c)!;
    }
    n.word = w;
  }
  const res: string[] = [];
  const m = board.length, nCols = board[0]!.length;
  const dfs = (r: number, c: number, node: Node) => {
    const ch = board[r]![c]!;
    const next = node.children.get(ch);
    if (!next) return;
    if (next.word) {
      res.push(next.word);
      next.word = null;
    }
    board[r]![c] = "#";
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]] as const) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < nCols && board[nr]![nc] !== "#") dfs(nr, nc, next);
    }
    board[r]![c] = ch;
    if (next.children.size === 0) node.children.delete(ch);
  };
  for (let r = 0; r < m; r++) for (let c = 0; c < nCols; c++) dfs(r, c, root);
  return res;
}

type Node = { children: Map<string, Node>; word: string | null };

export function findWords(board: string[][], words: string[]): string[] {
  const root: Node = { children: new Map(), word: null };
  for (const w of words) {
    let n = root;
    for (const c of w) {
      if (!n.children.has(c)) n.children.set(c, { children: new Map(), word: null });
      n = n.children.get(c)!;
    }
    n.word = w;
  }
  const res: string[] = [];
  const m = board.length, nCols = board[0]!.length;
  const dfs = (r: number, c: number, node: Node) => {
    const ch = board[r]![c]!;
    const next = node.children.get(ch);
    if (!next) return;
    if (next.word) {
      res.push(next.word);
      next.word = null;
    }
    board[r]![c] = "#";
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]] as const) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < nCols && board[nr]![nc] !== "#") dfs(nr, nc, next);
    }
    board[r]![c] = ch;
    if (next.children.size === 0) node.children.delete(ch);
  };
  for (let r = 0; r < m; r++) for (let c = 0; c < nCols; c++) dfs(r, c, root);
  return res;
}

Şablon bağlantısı

Trie kılavuzlu ızgara backtracking.

Yansıma

Sözlük trie’de. Tahtada DFS, önek trie’de yoksa dalı kes. Kelime bitince listeye ekle.
Aynı kelime iki hücreden bulunmasın diye bitiş bayrağını sil. Hücreyi geçici işaretle, dönüşte geri al.
Boş sözlük boş. Tahta harfi trie’de yoksa o başlangıç biter.