Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Backtracking

Guide 4 of 6 · Path 4 of 6

← PreviousNext →

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

Mediumbacktracking

Word Search

Problem (restated)

Given an m×n board of characters and a word, return true if the word exists on the board. Adjacent cells (4-dir) form the word; no cell is reused.

Intuition

Try every start cell. DFS match next letter; mark cell used then undo.

Approaches

Grid DFS with mark/unmark

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

Idea. dfs(r,c,i): if i==L done; if OOB or mismatch fail; set board to ‘#’, try 4 dirs, restore.

Walkthrough. board has A B C E / S F C S / A D E E, word=ABCCED → true along a path.

Trade-offs. L = word length. Prune early on mismatch; no extra visited matrix needed.

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

Template connection

Backtracking on a grid with choose/explore/undo.

Reflection