Problem Statement in English

You’re given a 2D grid of characters and a word. Your task is to determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Approach

We’re going to have to explore each cell of the grid and expand looking for the next character in the word. We can do this using a depth-first search (DFS) approach.

In order to avoid revisiting cells, we can mark them as visited by changing their value temporarily. After exploring all possible paths from a cell, we will backtrack and restore the original value of the cell. This has the advantage of not needing extra space for a visited set or array.

And we’re done!

Solution in Python


class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])

        def dfs(r: int, c: int, idx: int) -> bool:
            if idx == len(word):
                return True

            if (r < 0 or r >= ROWS or 
                c < 0 or c >= COLS or 
                board[r][c] != word[idx]):
                return False

            # Mark cell as visited in-place
            temp = board[r][c]
            board[r][c] = '#'

            # Explore 4 directions
            found = (dfs(r + 1, c, idx + 1) or
                     dfs(r - 1, c, idx + 1) or
                     dfs(r, c + 1, idx + 1) or
                     dfs(r, c - 1, idx + 1))

            # Backtrack / restore original character
            board[r][c] = temp
            return found

        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True

        return False

Complexity

  • Time: $O(m \times n \times 3^l)$
    Where $m$ is the number of rows, $n$ is the number of columns, and $l$ is the length of the word.

    This is because we have to explore all the cells in the grid, and for each cell, we can explore 3 directions (not 4 since we don’t explore the path we just came from) for each character in the word of length l.

  • Space: $O(l)$
    Since we are using recursion, the maximum depth of the recursion stack will be equal to the length of the word l.

And we are done.