Skip to main content

18. Word Search

mediumAsked at GitHub

Backtracking DFS on a grid to find a word path, testing the same traversal and backtracking patterns used in code-search substring matching across file content.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m×n character grid and a word, return true if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically) where each cell may be used only once.

Constraints

  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • grid and word consist of only uppercase and lowercase English letters

Examples

Example 1

Input
board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCCED'
Output
true

Example 2

Input
board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'SEE'
Output
true

Approaches

1. DFS without backtracking

Visit neighbors but never unmark visited cells — produces incorrect results because cells can't be reused but previously marked cells block valid paths.

Time
O(m*n*4^L)
Space
O(L)
// Incorrect: marks cells visited but never restores them
// Missed valid paths when starting cell is used, then unneeded

Tradeoff:

2. Backtracking DFS

For each cell matching word[0], run DFS: mark cell temporarily (e.g., '#'), recurse on four neighbors for word[1..], then restore cell on backtrack. Prune early on mismatch.

Time
O(m*n*3^L)
Space
O(L)
function exist(board, word) {
  const m = board.length, n = board[0].length;
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r<0||r>=m||c<0||c>=n||board[r][c]!==word[idx]) return false;
    const tmp = board[r][c];
    board[r][c] = '#';
    const found = dfs(r+1,c,idx+1)||dfs(r-1,c,idx+1)||dfs(r,c+1,idx+1)||dfs(r,c-1,idx+1);
    board[r][c] = tmp;
    return found;
  }
  for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (dfs(i,j,0)) return true;
  return false;
}

Tradeoff:

GitHub-specific tips

GitHub values clean backtracking implementations; a quick win is adding an early frequency-check pruning step (count character frequencies in word vs board) before starting DFS to fail fast.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Word Search and other GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →