#43 · Backtracking

Word Search

Given an m × n grid of letters and a word, return true if the word can be constructed from letters of sequentially adjacent cells (horizontal or vertical), using each cell at most once.

MediumLeetCode

Computing
Depends on
Answer

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Backtracking on a grid (DFS with undo)

Depth-first search that extends a path one cell at a time, mark each cell as used, and unmark it when the path is abandoned. The path is at most as long as the word, so the recursion is shallow even on a large grid.

Memory layout

The grid itself plus a recursion stack of at most word-length frames. A visited marker is either a second matrix, a hash set, or an overwritten character in the grid.

Operation	Cost
time	O(m·n·3^L), L = word length (3 choices after the first step)
space	O(L) recursion; no extra grid when marking in place

Visited marking strategies

Copied set per step, a separate boolean matrix, or in-place overwrite. All encode "this cell is on the current path"; they differ only in time and memory overhead.

Memory layout

Copied set: O(L) per call. Matrix: O(m·n) once. In place: zero extra, but it temporarily mutates the input.

Operation	Cost
mark / check	O(1) for the matrix and in place; O(L) to copy a set

Why it fits

The question is whether some path exists, and each step has a few choices that can be abandoned: the textbook shape for backtracking.
A letter mismatch cuts the whole subtree immediately, so most branches die after one or two cells.
Marking and restoring a cell is exactly what enforces "no cell used twice" for the current path while leaving it free for other paths.

Why alternatives degrade

BFS over (cell, position):: Breadth-first search cannot remember which cells this particular path has used, so it would allow reusing a cell.
Dynamic programming over (cell, k):: The "no reuse" rule depends on the entire path, not just the current cell, so subproblems do not repeat in a reusable way.
Global visited array that is never reset:: A cell used by a failed path would stay blocked for later paths that could legitimately use it.

Four approaches, from naive to production

1 · beginner

DFS that copies the visited set

time O(m·n·3^L · L)space O(L²) for the copies on the recursion stack

Try every cell as a start. Recurse over the four neighbours; at each step copy the set of used cells and add the current one, so each branch has its own history with no undo needed.

bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
    function<bool(int, int, int, set<string>)> dfs = [&](int r, int c, int k, set<string> visited) -> bool {
        if (k == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        string key = to_string(r) + "," + to_string(c);
        if (visited.count(key) || board[r][c] != word[k]) return false;
        set<string> next = visited;
        next.insert(key);
        return dfs(r + 1, c, k + 1, next) || dfs(r - 1, c, k + 1, next) || dfs(r, c + 1, k + 1, next) || dfs(r, c - 1, k + 1, next);
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(r, c, 0, {})) return true;
        }
    }
    return false;
}

public boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(board, word, r, c, 0, new HashSet<>())) return true;
        }
    }
    return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int k, Set<String> visited) {
    if (k == word.length()) return true;
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
    String key = r + "," + c;
    if (visited.contains(key) || board[r][c] != word.charAt(k)) return false;
    Set<String> next = new HashSet<>(visited);
    next.add(key);
    return dfs(board, word, r + 1, c, k + 1, next) || dfs(board, word, r - 1, c, k + 1, next) || dfs(board, word, r, c + 1, k + 1, next) || dfs(board, word, r, c - 1, k + 1, next);
}

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, k, visited):
        if k == len(word): return True
        if r < 0 or c < 0 or r >= rows or c >= cols: return False
        key = (r, c)
        if key in visited or board[r][c] != word[k]: return False
        nxt = set(visited)
        nxt.add(key)
        return dfs(r + 1, c, k + 1, nxt) or dfs(r - 1, c, k + 1, nxt) or dfs(r, c + 1, k + 1, nxt) or dfs(r, c - 1, k + 1, nxt)
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0, set()): return True
    return False

function exist(board: string[][], word: string): boolean {
  const rows = board.length, cols = board[0].length;
  const dfs = (r: number, c: number, k: number, visited: Set<string>): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    const key = r + ',' + c;
    if (visited.has(key) || board[r][c] !== word[k]) return false;
    const next = new Set(visited);
    next.add(key);
    return dfs(r + 1, c, k + 1, next) || dfs(r - 1, c, k + 1, next) || dfs(r, c + 1, k + 1, next) || dfs(r, c - 1, k + 1, next);
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0, new Set())) return true;
    }
  }
  return false;
}

Flaws & bottlenecks

Copying a set at each step multiplies the cost of every call by the path length.
Cells are stored as text keys ("r,c"), so each check builds and hashes a string.
It allocates a new set for every visited cell: heavy garbage and cache pressure.

Interviewer cross-questions

Why does copying avoid the need to undo?

Say: Each branch gets its own private set, so a sibling branch never sees marks made by another. The price is the copy at every step.

Can you avoid the copy but keep correctness?

Say: Yes: use one shared structure, set the mark before recursing and clear it afterwards. That is backtracking, and it makes each step O(1).

What is the time complexity?

Say: From each of the m·n starts, the first step has up to 4 choices and later steps up to 3, giving O(m·n·3^L) paths; copying multiplies by L.

2 · intermediate

Visited matrix with undo

time O(m·n·3^L)space O(m·n + L)

Keep one boolean matrix for the whole search. Mark a cell before exploring its neighbours and unmark it afterwards, so the matrix always describes exactly the current path.

bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    function<bool(int, int, int)> dfs = [&](int r, int c, int k) -> bool {
        if (k == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        if (visited[r][c] || board[r][c] != word[k]) return false;
        visited[r][c] = true;
        bool found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
        visited[r][c] = false;
        return found;
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

public boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    boolean[][] visited = new boolean[rows][cols];
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(board, word, visited, r, c, 0)) return true;
        }
    }
    return false;
}
private boolean dfs(char[][] board, String word, boolean[][] visited, int r, int c, int k) {
    if (k == word.length()) return true;
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
    if (visited[r][c] || board[r][c] != word.charAt(k)) return false;
    visited[r][c] = true;
    boolean found = dfs(board, word, visited, r + 1, c, k + 1) || dfs(board, word, visited, r - 1, c, k + 1) || dfs(board, word, visited, r, c + 1, k + 1) || dfs(board, word, visited, r, c - 1, k + 1);
    visited[r][c] = false;
    return found;
}

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]
    def dfs(r, c, k):
        if k == len(word): return True
        if r < 0 or c < 0 or r >= rows or c >= cols: return False
        if visited[r][c] or board[r][c] != word[k]: return False
        visited[r][c] = True
        found = dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1) or dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1)
        visited[r][c] = False
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

function exist(board: string[][], word: string): boolean {
  const rows = board.length, cols = board[0].length;
  const visited = Array.from({ length: rows }, () => new Array<boolean>(cols).fill(false));
  const dfs = (r: number, c: number, k: number): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    if (visited[r][c] || board[r][c] !== word[k]) return false;
    visited[r][c] = true;
    const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
    visited[r][c] = false;
    return found;
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Flaws & bottlenecks

Needs an extra m × n matrix of flags.
Bounds are checked on entry to every call, including for neighbours that are obviously outside.
Four near-identical recursive calls on one line are easy to mistype.

Interviewer cross-questions

Why must you unmark after the recursion?

Say: The mark means "on the current path". When the path is abandoned the cell is available again, and a different path or start may need it.

What if the unmark is skipped on success?

Say: It does not matter for the boolean answer because the search stops, but the matrix would be left dirty, which is a bug if the structure is reused.

How could you remove the extra matrix?

Say: Overwrite the board cell with a sentinel character while it is on the path, then restore it. That uses the input grid as the visited marker.

3 · advanced

In-place marking + direction table

time O(m·n·3^L)space O(L)

Mark the current cell by overwriting it with a character that can never match, loop over a table of four moves instead of writing four calls, and restore the cell on the way back.

bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    function<bool(int, int, int)> dfs = [&](int r, int c, int k) -> bool {
        if (k == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        if (board[r][c] != word[k]) return false;
        char saved = board[r][c];
        board[r][c] = '#';
        bool found = false;
        for (auto& d : dirs) {
            if (dfs(r + d[0], c + d[1], k + 1)) {
                found = true;
                break;
            }
        }
        board[r][c] = saved;
        return found;
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

public boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(board, word, dirs, r, c, 0)) return true;
        }
    }
    return false;
}
private boolean dfs(char[][] board, String word, int[][] dirs, int r, int c, int k) {
    if (k == word.length()) return true;
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
    if (board[r][c] != word.charAt(k)) return false;
    char saved = board[r][c];
    board[r][c] = '#';
    boolean found = false;
    for (int[] d : dirs) {
        if (dfs(board, word, dirs, r + d[0], c + d[1], k + 1)) {
            found = true;
            break;
        }
    }
    board[r][c] = saved;
    return found;
}

def exist(board, word):
    rows, cols = len(board), len(board[0])
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    def dfs(r, c, k):
        if k == len(word): return True
        if r < 0 or c < 0 or r >= rows or c >= cols: return False
        if board[r][c] != word[k]: return False
        saved = board[r][c]
        board[r][c] = '#'
        found = False
        for dr, dc in dirs:
            if dfs(r + dr, c + dc, k + 1):
                found = True
                break
        board[r][c] = saved
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

function exist(board: string[][], word: string): boolean {
  const rows = board.length, cols = board[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  const dfs = (r: number, c: number, k: number): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    if (board[r][c] !== word[k]) return false;
    const saved = board[r][c];
    board[r][c] = '#';
    let found = false;
    for (const [dr, dc] of dirs) {
      if (dfs(r + dr, c + dc, k + 1)) {
        found = true;
        break;
      }
    }
    board[r][c] = saved;
    return found;
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Flaws & bottlenecks

Temporarily mutates the input, which is unsafe if other threads read the board or if the board can contain the sentinel.
The restore must run on every exit path, or the board is corrupted.
Still tries every cell as a start, even letters that cannot begin the word.

Interviewer cross-questions

Why is mutating the board risky?

Say: If the code exits without restoring, or another thread reads the board, the data is wrong. A production version either copies the board or guarantees exclusive access.

What if the board might contain "#"?

Say: Choose a sentinel outside the alphabet (for example a character code that cannot occur), or use a separate visited structure.

How would you speed up unsolvable words?

Say: Count letters first: if the board does not contain enough of some letter, answer false immediately. Also start from the rarer end of the word.

4 · expert

Letter counts, rarer end first, guard before call

time O(m·n + 3^L · starts); much faster on hard inputsspace O(L + alphabet)

Reject impossible words early (too long, or not enough of some letter). If the first letter is more common than the last, reverse the word so the search has fewer starting cells. Check the bounds before each recursive call and return as soon as the last letter matches.

bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
    if ((int)word.size() > rows * cols) return false;
    map<char, int> count;
    for (auto& row : board) {
        for (char ch : row) count[ch]++;
    }
    map<char, int> need;
    for (char ch : word) need[ch]++;
    for (auto& [ch, n] : need) {
        if (count[ch] < n) return false;
    }
    if (count[word.front()] > count[word.back()]) {
        reverse(word.begin(), word.end());
    }
    function<bool(int, int, int)> dfs = [&](int r, int c, int k) -> bool {
        if (board[r][c] != word[k]) return false;
        if (k == (int)word.size() - 1) return true;
        char saved = board[r][c];
        board[r][c] = '#';
        bool found =
            (r > 0 && dfs(r - 1, c, k + 1)) ||
            (c > 0 && dfs(r, c - 1, k + 1)) ||
            (r + 1 < rows && dfs(r + 1, c, k + 1)) ||
            (c + 1 < cols && dfs(r, c + 1, k + 1));
        board[r][c] = saved;
        return found;
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

public boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    if (word.length() > rows * cols) return false;
    Map<Character, Integer> count = new HashMap<>();
    for (char[] row : board) {
        for (char ch : row) count.merge(ch, 1, Integer::sum);
    }
    Map<Character, Integer> need = new HashMap<>();
    for (char ch : word.toCharArray()) need.merge(ch, 1, Integer::sum);
    for (Map.Entry<Character, Integer> e : need.entrySet()) {
        if (count.getOrDefault(e.getKey(), 0) < e.getValue()) return false;
    }
    if (count.getOrDefault(word.charAt(0), 0) > count.getOrDefault(word.charAt(word.length() - 1), 0)) {
        word = new StringBuilder(word).reverse().toString();
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(board, word, r, c, 0)) return true;
        }
    }
    return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int k) {
    if (board[r][c] != word.charAt(k)) return false;
    if (k == word.length() - 1) return true;
    char saved = board[r][c];
    board[r][c] = '#';
    boolean found =
        (r > 0 && dfs(board, word, r - 1, c, k + 1)) ||
        (c > 0 && dfs(board, word, r, c - 1, k + 1)) ||
        (r + 1 < board.length && dfs(board, word, r + 1, c, k + 1)) ||
        (c + 1 < board[0].length && dfs(board, word, r, c + 1, k + 1));
    board[r][c] = saved;
    return found;
}

def exist(board, word):
    rows, cols = len(board), len(board[0])
    if len(word) > rows * cols: return False
    count = {}
    for row in board:
        for ch in row: count[ch] = count.get(ch, 0) + 1
    need = {}
    for ch in word: need[ch] = need.get(ch, 0) + 1
    for ch, n in need.items():
        if count.get(ch, 0) < n: return False
    if count.get(word[0], 0) > count.get(word[-1], 0):
        word = word[::-1]
    def dfs(r, c, k):
        if board[r][c] != word[k]: return False
        if k == len(word) - 1: return True
        saved = board[r][c]
        board[r][c] = '#'
        found = ((r > 0 and dfs(r - 1, c, k + 1)) or
                 (c > 0 and dfs(r, c - 1, k + 1)) or
                 (r + 1 < rows and dfs(r + 1, c, k + 1)) or
                 (c + 1 < cols and dfs(r, c + 1, k + 1)))
        board[r][c] = saved
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

function exist(board: string[][], word: string): boolean {
  const rows = board.length, cols = board[0].length;
  if (word.length > rows * cols) return false;
  const count = new Map<string, number>();
  for (const row of board) {
    for (const ch of row) count.set(ch, (count.get(ch) ?? 0) + 1);
  }
  const need = new Map<string, number>();
  for (const ch of word) need.set(ch, (need.get(ch) ?? 0) + 1);
  for (const [ch, n] of need) {
    if ((count.get(ch) ?? 0) < n) return false;
  }
  if ((count.get(word[0]) ?? 0) > (count.get(word[word.length - 1]) ?? 0)) {
    word = [...word].reverse().join('');
  }
  const dfs = (r: number, c: number, k: number): boolean => {
    if (board[r][c] !== word[k]) return false;
    if (k === word.length - 1) return true;
    const saved = board[r][c];
    board[r][c] = '#';
    const found =
      (r > 0 && dfs(r - 1, c, k + 1)) ||
      (c > 0 && dfs(r, c - 1, k + 1)) ||
      (r + 1 < rows && dfs(r + 1, c, k + 1)) ||
      (c + 1 < cols && dfs(r, c + 1, k + 1));
    board[r][c] = saved;
    return found;
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Flaws & bottlenecks

More code and more cases to test than the plain DFS.
The pre-checks do not change the worst case: a board full of the same letter with a long word of that letter is still exponential.
Still mutates the board in place (restore on every path).

Interviewer cross-questions

Why does reversing the word still give the right answer?

Say: A path of adjacent cells spelling the word forwards also spells its reverse when read backwards. Searching for the reversed word finds the same set of cells.

Why check counts first?

Say: It is O(m·n + L) and turns many impossible inputs (the classic worst-case test cases) into an instant false instead of an exponential search.

Why check bounds before the call?

Say: It saves a function call per out-of-range neighbour, and lets the callee assume valid coordinates so it needs no bounds check of its own.

Synchronized code walkthrough

Showing: DFS that copies the visited set — shares the player above; click any step to jump.

bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
    function<bool(int, int, int, set<string>)> dfs = [&](int r, int c, int k, set<string> visited) -> bool {
        if (k == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        string key = to_string(r) + "," + to_string(c);
        if (visited.count(key) || board[r][c] != word[k]) return false;
        set<string> next = visited;
        next.insert(key);
        return dfs(r + 1, c, k + 1, next) || dfs(r - 1, c, k + 1, next) || dfs(r, c + 1, k + 1, next) || dfs(r, c - 1, k + 1, next);
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(r, c, 0, {})) return true;
        }
    }
    return false;
}

public boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(board, word, r, c, 0, new HashSet<>())) return true;
        }
    }
    return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int k, Set<String> visited) {
    if (k == word.length()) return true;
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
    String key = r + "," + c;
    if (visited.contains(key) || board[r][c] != word.charAt(k)) return false;
    Set<String> next = new HashSet<>(visited);
    next.add(key);
    return dfs(board, word, r + 1, c, k + 1, next) || dfs(board, word, r - 1, c, k + 1, next) || dfs(board, word, r, c + 1, k + 1, next) || dfs(board, word, r, c - 1, k + 1, next);
}

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, k, visited):
        if k == len(word): return True
        if r < 0 or c < 0 or r >= rows or c >= cols: return False
        key = (r, c)
        if key in visited or board[r][c] != word[k]: return False
        nxt = set(visited)
        nxt.add(key)
        return dfs(r + 1, c, k + 1, nxt) or dfs(r - 1, c, k + 1, nxt) or dfs(r, c + 1, k + 1, nxt) or dfs(r, c - 1, k + 1, nxt)
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0, set()): return True
    return False

function exist(board: string[][], word: string): boolean {
  const rows = board.length, cols = board[0].length;
  const dfs = (r: number, c: number, k: number, visited: Set<string>): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    const key = r + ',' + c;
    if (visited.has(key) || board[r][c] !== word[k]) return false;
    const next = new Set(visited);
    next.add(key);
    return dfs(r + 1, c, k + 1, next) || dfs(r - 1, c, k + 1, next) || dfs(r, c + 1, k + 1, next) || dfs(r, c - 1, k + 1, next);
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0, new Set())) return true;
    }
  }
  return false;
}

bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    function<bool(int, int, int)> dfs = [&](int r, int c, int k) -> bool {
        if (k == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        if (visited[r][c] || board[r][c] != word[k]) return false;
        visited[r][c] = true;
        bool found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
        visited[r][c] = false;
        return found;
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

public boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    boolean[][] visited = new boolean[rows][cols];
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(board, word, visited, r, c, 0)) return true;
        }
    }
    return false;
}
private boolean dfs(char[][] board, String word, boolean[][] visited, int r, int c, int k) {
    if (k == word.length()) return true;
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
    if (visited[r][c] || board[r][c] != word.charAt(k)) return false;
    visited[r][c] = true;
    boolean found = dfs(board, word, visited, r + 1, c, k + 1) || dfs(board, word, visited, r - 1, c, k + 1) || dfs(board, word, visited, r, c + 1, k + 1) || dfs(board, word, visited, r, c - 1, k + 1);
    visited[r][c] = false;
    return found;
}

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]
    def dfs(r, c, k):
        if k == len(word): return True
        if r < 0 or c < 0 or r >= rows or c >= cols: return False
        if visited[r][c] or board[r][c] != word[k]: return False
        visited[r][c] = True
        found = dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1) or dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1)
        visited[r][c] = False
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

function exist(board: string[][], word: string): boolean {
  const rows = board.length, cols = board[0].length;
  const visited = Array.from({ length: rows }, () => new Array<boolean>(cols).fill(false));
  const dfs = (r: number, c: number, k: number): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    if (visited[r][c] || board[r][c] !== word[k]) return false;
    visited[r][c] = true;
    const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
    visited[r][c] = false;
    return found;
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    function<bool(int, int, int)> dfs = [&](int r, int c, int k) -> bool {
        if (k == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        if (board[r][c] != word[k]) return false;
        char saved = board[r][c];
        board[r][c] = '#';
        bool found = false;
        for (auto& d : dirs) {
            if (dfs(r + d[0], c + d[1], k + 1)) {
                found = true;
                break;
            }
        }
        board[r][c] = saved;
        return found;
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

public boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(board, word, dirs, r, c, 0)) return true;
        }
    }
    return false;
}
private boolean dfs(char[][] board, String word, int[][] dirs, int r, int c, int k) {
    if (k == word.length()) return true;
    if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false;
    if (board[r][c] != word.charAt(k)) return false;
    char saved = board[r][c];
    board[r][c] = '#';
    boolean found = false;
    for (int[] d : dirs) {
        if (dfs(board, word, dirs, r + d[0], c + d[1], k + 1)) {
            found = true;
            break;
        }
    }
    board[r][c] = saved;
    return found;
}

def exist(board, word):
    rows, cols = len(board), len(board[0])
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    def dfs(r, c, k):
        if k == len(word): return True
        if r < 0 or c < 0 or r >= rows or c >= cols: return False
        if board[r][c] != word[k]: return False
        saved = board[r][c]
        board[r][c] = '#'
        found = False
        for dr, dc in dirs:
            if dfs(r + dr, c + dc, k + 1):
                found = True
                break
        board[r][c] = saved
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

function exist(board: string[][], word: string): boolean {
  const rows = board.length, cols = board[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  const dfs = (r: number, c: number, k: number): boolean => {
    if (k === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    if (board[r][c] !== word[k]) return false;
    const saved = board[r][c];
    board[r][c] = '#';
    let found = false;
    for (const [dr, dc] of dirs) {
      if (dfs(r + dr, c + dc, k + 1)) {
        found = true;
        break;
      }
    }
    board[r][c] = saved;
    return found;
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
    if ((int)word.size() > rows * cols) return false;
    map<char, int> count;
    for (auto& row : board) {
        for (char ch : row) count[ch]++;
    }
    map<char, int> need;
    for (char ch : word) need[ch]++;
    for (auto& [ch, n] : need) {
        if (count[ch] < n) return false;
    }
    if (count[word.front()] > count[word.back()]) {
        reverse(word.begin(), word.end());
    }
    function<bool(int, int, int)> dfs = [&](int r, int c, int k) -> bool {
        if (board[r][c] != word[k]) return false;
        if (k == (int)word.size() - 1) return true;
        char saved = board[r][c];
        board[r][c] = '#';
        bool found =
            (r > 0 && dfs(r - 1, c, k + 1)) ||
            (c > 0 && dfs(r, c - 1, k + 1)) ||
            (r + 1 < rows && dfs(r + 1, c, k + 1)) ||
            (c + 1 < cols && dfs(r, c + 1, k + 1));
        board[r][c] = saved;
        return found;
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

public boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    if (word.length() > rows * cols) return false;
    Map<Character, Integer> count = new HashMap<>();
    for (char[] row : board) {
        for (char ch : row) count.merge(ch, 1, Integer::sum);
    }
    Map<Character, Integer> need = new HashMap<>();
    for (char ch : word.toCharArray()) need.merge(ch, 1, Integer::sum);
    for (Map.Entry<Character, Integer> e : need.entrySet()) {
        if (count.getOrDefault(e.getKey(), 0) < e.getValue()) return false;
    }
    if (count.getOrDefault(word.charAt(0), 0) > count.getOrDefault(word.charAt(word.length() - 1), 0)) {
        word = new StringBuilder(word).reverse().toString();
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (dfs(board, word, r, c, 0)) return true;
        }
    }
    return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int k) {
    if (board[r][c] != word.charAt(k)) return false;
    if (k == word.length() - 1) return true;
    char saved = board[r][c];
    board[r][c] = '#';
    boolean found =
        (r > 0 && dfs(board, word, r - 1, c, k + 1)) ||
        (c > 0 && dfs(board, word, r, c - 1, k + 1)) ||
        (r + 1 < board.length && dfs(board, word, r + 1, c, k + 1)) ||
        (c + 1 < board[0].length && dfs(board, word, r, c + 1, k + 1));
    board[r][c] = saved;
    return found;
}

def exist(board, word):
    rows, cols = len(board), len(board[0])
    if len(word) > rows * cols: return False
    count = {}
    for row in board:
        for ch in row: count[ch] = count.get(ch, 0) + 1
    need = {}
    for ch in word: need[ch] = need.get(ch, 0) + 1
    for ch, n in need.items():
        if count.get(ch, 0) < n: return False
    if count.get(word[0], 0) > count.get(word[-1], 0):
        word = word[::-1]
    def dfs(r, c, k):
        if board[r][c] != word[k]: return False
        if k == len(word) - 1: return True
        saved = board[r][c]
        board[r][c] = '#'
        found = ((r > 0 and dfs(r - 1, c, k + 1)) or
                 (c > 0 and dfs(r, c - 1, k + 1)) or
                 (r + 1 < rows and dfs(r + 1, c, k + 1)) or
                 (c + 1 < cols and dfs(r, c + 1, k + 1)))
        board[r][c] = saved
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

function exist(board: string[][], word: string): boolean {
  const rows = board.length, cols = board[0].length;
  if (word.length > rows * cols) return false;
  const count = new Map<string, number>();
  for (const row of board) {
    for (const ch of row) count.set(ch, (count.get(ch) ?? 0) + 1);
  }
  const need = new Map<string, number>();
  for (const ch of word) need.set(ch, (need.get(ch) ?? 0) + 1);
  for (const [ch, n] of need) {
    if ((count.get(ch) ?? 0) < n) return false;
  }
  if ((count.get(word[0]) ?? 0) > (count.get(word[word.length - 1]) ?? 0)) {
    word = [...word].reverse().join('');
  }
  const dfs = (r: number, c: number, k: number): boolean => {
    if (board[r][c] !== word[k]) return false;
    if (k === word.length - 1) return true;
    const saved = board[r][c];
    board[r][c] = '#';
    const found =
      (r > 0 && dfs(r - 1, c, k + 1)) ||
      (c > 0 && dfs(r, c - 1, k + 1)) ||
      (r + 1 < rows && dfs(r + 1, c, k + 1)) ||
      (c + 1 < cols && dfs(r, c + 1, k + 1));
    board[r][c] = saved;
    return found;
  };
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}