Skip to main content

19. Word Search

mediumAsked at Roblox

Find whether a word exists in a 2D character grid following adjacent cells — Roblox uses the same constrained-path DFS to validate item-placement patterns and check chat-filter word formations across tiled regions.

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

Problem

Given an m x 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). The same cell may not be used more than once.

Constraints

  • m == board.length, n == board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board[i][j] and word consist only of 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

Approaches

1. Brute force — DFS with visited set

Start DFS from every cell, use a Set to track visited coordinates in the current path, backtrack on mismatch.

Time
O(m*n * 4^L) where L = word length
Space
O(L) for visited set
function exist(board, word) {
  const rows = board.length, cols = board[0].length;
  const visited = new Set();

  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;
    const key = r * cols + c;
    if (visited.has(key)) return false;
    visited.add(key);
    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);
    visited.delete(key);
    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;
}

Tradeoff:

2. Optimal — DFS with in-place marking

Mark the current cell with a sentinel character during recursion and restore it on backtrack, eliminating the visited Set's overhead.

Time
O(m*n * 4^L)
Space
O(L) call stack only
function exist(board, word) {
  const rows = board.length, cols = board[0].length;

  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;
    const temp = 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] = temp;
    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;
}

Tradeoff:

Roblox-specific tips

Roblox interviewers appreciate the in-place sentinel trick because game-engine code is memory-tight; allocating a visited data structure per search call adds up when running thousands of tile validations per frame. They also ask about pruning: if the remaining grid cells containing the next character are fewer than the remaining word length, you can short-circuit early.

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

Practice these live with InterviewChamp.AI →