Frontend Beauty
ESC

Type to search the knowledge base.

Word Search

Does a word exist on a letter grid? Backtracking DFS from each cell with visited marks.

intermediate3 min read
  • dsa
  • backtracking
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

m × n board of characters and a string word. Return true if word exists in the grid: consecutive letters adjacent 4-directionally, no cell reused in one path.

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]]
word = "ABCCED" → true
word = "SEE"    → true
word = "ABCB"   → false

Brute force

From every starting cell matching word[0], DFS the path.

This is the standard solution — exponential in word length but expected.

Optimal (standard): DFS backtracking

function exist(board: string[][], word: string): boolean {
  const rows = board.length;
  const cols = board[0].length;

  function dfs(r: number, c: number, i: number): boolean {
    if (i === word.length) return true;
    if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
    if (board[r][c] !== word[i]) return false;

    const tmp = board[r][c];
    board[r][c] = "#"; // visit
    const found =
      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] = tmp;
    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;
}
Time O(m · n · 4^L) worst, L = word length
Space O(L) recursion

Small prunes

  • Count letter frequencies on board vs word; reject early if impossible
  • Reverse word if last char is rarer (start from rarer end) — micro-opt

Edge cases

  • Single cell board
  • Word longer than m·n → false
  • Multiple same letters requiring careful visit marks
  • Word uses same letter value on different cells

Common bugs

  • Not unmarking visited
  • Checking i === word.length after bounds (order matters)
  • 8-dir by mistake
  • Reusing cell

Interview delivery

  1. Start DFS at each matching cell.
  2. Mark / recurse / unmark.
  3. Complexity exponential in L.
  4. For many words → Word Search II + trie.

Why mark with '#'

Mutating the board avoids an O(mn) visited matrix and is cache-friendly. Restore after exploring so other paths see the original letter. Never leave '#' if the function returns true early without cleanup on other branches — restore on the way back always (the tmp pattern does).

Order of base cases

Check i === word.length before bounds/character checks when you increment i on entry… In the template above, we check length first at the top of dfs after moving into a cell via the character match of the previous frame. Alternative style: match char, then recurse with i+1, success when i+1 === length. Both fine; pick one and stick to it.

When it TLEs

Worst boards with repeated letters (all As) and long words explode. Pruning: frequency precheck; start from rarer end of the word. Mention for follow-up performance chat.

Further reading