Skip to main content

79. Word Search

mediumAsked at Canva

Determine whether a word exists as a connected path of adjacent letters in a character grid — Canva uses grid-backtracking problems to evaluate candidates who will work on spatially-aware features like auto-snapping, object search, and canvas hit-testing.

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

Problem

Given an m×n grid of characters and a string word, return true if the word exists in the grid. The word must be constructed from letters of sequentially adjacent cells (horizontally or vertically neighboring), and the same cell may not be used more than once.

Constraints

  • m == board.length
  • n == board[0].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 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

Example 3

Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output
false

Explanation: 'B' at (0,1) cannot be reused to close the path.

Approaches

1. DFS backtracking with visited set

Try every cell as a starting point; DFS in 4 directions matching the next character, tracking visited cells in a set and backtracking when a direction fails.

Time
O(m*n*4^L) where L = word length
Space
O(L)
function exist(board, word) {
  const m = board.length;
  const n = board[0].length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    if (board[r][c] !== word[idx]) return false;
    const tmp = board[r][c];
    board[r][c] = '#'; // mark visited
    for (const [dr, dc] of dirs) {
      if (dfs(r + dr, c + dc, idx + 1)) {
        board[r][c] = tmp;
        return true;
      }
    }
    board[r][c] = tmp; // restore
    return false;
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Tradeoff:

2. DFS backtracking with frequency pruning

Add a pre-check: count character frequencies in the board and the word; if the word requires more of any character than the board contains, return false immediately — prunes many branches before DFS starts.

Time
O(m*n*4^L)
Space
O(L)
function exist(board, word) {
  const m = board.length;
  const n = board[0].length;
  // Frequency pruning
  const boardFreq = {};
  for (const row of board) {
    for (const ch of row) {
      boardFreq[ch] = (boardFreq[ch] || 0) + 1;
    }
  }
  for (const ch of word) {
    if (!boardFreq[ch]) return false;
    boardFreq[ch]--;
  }
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  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] = '#';
    for (const [dr, dc] of dirs) {
      if (dfs(r + dr, c + dc, idx + 1)) {
        board[r][c] = tmp;
        return true;
      }
    }
    board[r][c] = tmp;
    return false;
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
  return false;
}

Tradeoff:

Canva-specific tips

Canva interviewers watch closely for the visited-cell technique: marking a cell with a sentinel character (e.g. '#') during recursion and restoring it on backtrack avoids a separate visited array and is O(1) extra space per level. The more memorable pitfall is forgetting the restore step after early-return — trace the code path where `dfs` returns true mid-recursion and confirm you restore before returning. The frequency pruning pre-check is a strong differentiator: it can eliminate entire search trees in seconds for adversarial inputs.

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 Canva interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →