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

Mediumbacktracking

Word Search

Problem (yeniden ifade)

Karakterlerden m×n tahta ve bir kelime verilir. Kelime tahtada varsa true. Bitşik hücreler (4 yön) kelimeyi oluşturur; hücre yeniden kullanılmaz.

Sezgi

Her başlangıç hücresini dene. DFS ile sonraki harfi eşleştir; hücreyi kullanıldı işaretle, sonra geri al.

Yaklaşımlar

İşaretle/geri al ızgara DFS

Tested only

Time O(m·n·4^L)Space O(L)

Fikir. dfs(r,c,i): i==L bitti; sınır dışı veya uyuşmazlık fail; board’u ‘#’, 4 yön dene, geri yükle.

Adım adım. board A B C E / S F C S / A D E E, word=ABCCED → bir yol boyunca true.

Ödünleşimler. L = kelime uzunluğu. Uyuşmazlıkta erken budama; ekstra visited matrisi gerekmez.

Solution

export function exist(board: string[][], word: string): boolean {
  const m = board.length;
  const n = board[0]!.length;
  const dfs = (r: number, c: number, i: number): boolean => {
    if (i === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r]![c] !== word[i]) return false;
    const ch = board[r]![c]!;
    board[r]![c] = "#";
    const ok =
      dfs(r + 1, c, i + 1) ||
      dfs(r - 1, c, i + 1) ||
      dfs(r, c + 1, i + 1) ||
      dfs(r, c - 1, i + 1);
    board[r]![c] = ch;
    return ok;
  };
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

export function exist(board: string[][], word: string): boolean {
  const m = board.length;
  const n = board[0]!.length;
  const dfs = (r: number, c: number, i: number): boolean => {
    if (i === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n || board[r]![c] !== word[i]) return false;
    const ch = board[r]![c]!;
    board[r]![c] = "#";
    const ok =
      dfs(r + 1, c, i + 1) ||
      dfs(r - 1, c, i + 1) ||
      dfs(r, c + 1, i + 1) ||
      dfs(r, c - 1, i + 1);
    board[r]![c] = ch;
    return ok;
  };
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Şablon bağlantısı

Seç / keşfet / geri al ile ızgara üzerinde backtracking.

Yansıma

Bu problemi 90 saniye içinde hangi kalıp ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?