MediumBacktrackingRecursionMatrix

Word Search

1 approach, code in every language

You are given a grid of characters with m rows and n columns along with a target word. Decide whether the word can be traced through the grid by moving between cells that share an edge, that is up, down, left, or right. The path must spell the word in order and may not reuse the same cell more than once.

Return true if such a path exists anywhere in the grid, and false otherwise. Diagonal moves are not allowed.

Example 1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

Starting at the top-left A, the path A to B to C to C to E to D stays adjacent and reuses no cell.

Example 2

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

Output: false

Reaching the final B would require stepping back onto the already-used B cell, which is not allowed.

Constraints

1 <= board.length, board[0].length <= 6
1 <= word.length <= 15
board and word contain only English letters

Depth-first search with in-place marking

Try each grid cell as a starting point, then explore the four neighbors recursively, temporarily marking visited cells so a path never reuses a square.

Loading animation…

Intuition

Every occurrence of the word must begin at some cell whose character matches the first letter, so we launch a search from each cell. From a matching cell we attempt to extend the match into any of the four orthogonal neighbors for the next letter. To respect the no-reuse rule we overwrite the current cell with a placeholder before recursing and restore it afterward, which acts as an on-the-fly visited set without extra memory. A branch succeeds the moment the entire word has been matched.

Algorithm walkthrough

1Loop over every cell and start a search whenever it could match the first character.
2In the search, if the matched length equals the word length, report success.
3If the position is out of bounds or the character does not match the expected letter, fail this branch.
4Mark the current cell with a placeholder, then search up, down, left, and right for the next letter.
5Restore the original character before returning so other paths can reuse the cell.

Implementation

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

        def backtrack(r: int, c: int, index: int) -> bool:
            if index == len(word):
                return True
            if (r < 0 or r >= rows or c < 0 or c >= cols
                    or board[r][c] != word[index]):
                return False
            temp = board[r][c]
            board[r][c] = "#"
            found = (
                backtrack(r + 1, c, index + 1)
                or backtrack(r - 1, c, index + 1)
                or backtrack(r, c + 1, index + 1)
                or backtrack(r, c - 1, index + 1)
            )
            board[r][c] = temp
            return found

        for r in range(rows):
            for c in range(cols):
                if backtrack(r, c, 0):
                    return True
        return False

Time

O(m * n * 4^L)

Space

O(L)

L is the word length; the recursion stack goes at most L deep and marking is done in place.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Tablet Glyph Trail is our own problem on the technique behind Word Search: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free