SolutionGigsSolutionGigs
L3 · FAANGBacktracking~18 min · 5 tests

Word Search in a Grid

Find whether a word exists in a letter grid along adjacent cells without reusing a cell, using DFS backtracking with in-place marking. Common FAANG medium.

The problem

board is a list of strings. Return True if word can be traced through horizontally or vertically adjacent cells, using each cell at most once.

Examples

  1. Example 1

    Input

    exist(['ABCE', 'SFCS', 'ADEE'], 'ABCCED')

    Expected output

    True

  2. Example 2

    Input

    exist(['ABCE', 'SFCS', 'ADEE'], 'ABCB')

    Expected output

    False

+ 3 hidden tests on Submit — cannot reuse a cell.

Edge cases to ask about

  • Reusing a cell
  • Single cell

Hints

0/3

    How an interviewer scores this

    0/9
    Python 3.13 · exist
    ⌘/Ctrl + Enter runs the examples

    Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

    Complexity Lab

    What does this cost as n grows?

    Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

    Time complexity of the optimal solution
    Space complexity (extra memory)

    Pick both to reveal the answer.

    From brute force to optimal

    The progression an interviewer wants to hear, one step at a time.

    ApproachTimeSpaceIdea
    DFS from every cell + backtrackingO(R·C · 3ᴸ)O(L)After the first step each move has at most 3 new directions.
    Walkthrough of the optimal approach (try it yourself first)

    DFS from every cell. At each step the cell must match the next letter. Mark it as used ("#") before recursing into the 4 neighbours, and restore it afterwards so other paths can use it. Returning as soon as one path succeeds prunes the rest.

    Pruning ideas worth mentioning: give up early if the board doesn't have enough of some letter, and search from the rarer end of the word.

    Complexity: O(R·C · 3ᴸ) time, O(L) space. From each of R·C starts, the path branches into at most 3 new directions for each of the L letters; recursion depth is L.

    Reveal the reference solution
    def exist(board, word):
    if not word:
        return True
    grid = [list(row) for row in board]
    rows, cols = len(grid), len(grid[0]) if grid else 0

    def dfs(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != word[i]:
            return False
        saved, grid[r][c] = grid[r][c], "#"           # mark as used
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        grid[r][c] = saved                             # un-choose
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

    Follow-ups interviewers ask

    • Find every dictionary word on the board (trie + DFS).

    Frequently asked interview questions

    Core interview concepts, complexities, and follow-ups scored by hiring teams.

    What is the time complexity of Word Search in a Grid in Python?

    The optimal solution runs in O(R·C · 3ᴸ) time and O(L) auxiliary space. From each of R·C starts, the path branches into at most 3 new directions for each of the L letters; recursion depth is L.

    What follow-up questions do interviewers ask about Word Search in a Grid?

    Find every dictionary word on the board (trie + DFS).

    Practise the same pattern