Word Search

Problem

https://leetcode.com/problems/word-search/

Given an m x n grid of characters board and a string word, return true if 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.

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

Constraints:

• m == board.length

• n = board[i].length

• 1 <= m, n <= 6

• 1 <= word.length <= 15

• boardand word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Pattern

Array, String, Backtracking, Depth-First Search, Matrix

Approaches

Backtracking

Explanation

To solve Word Search, we need to iterate through each cell in the board and check if we can find the word starting from that cell. Starting from a cell, explore in all four directions, checking if the next character in the word matches the character in the board. We stop if we reach the end of the word (success) or if we go out of bounds, the character does not match, or we revisit an already visited cell (failure).

To track visited cells, we can temporarily mark the cell as visited by changing its value to “#” and then restore it after exploring all directions. Because we are using DFS, we only explore one search path at a time, and we restore the cell’s original value after exploring a path.

Code

def exist(board: list[list[str]], word: str) -> bool:
    """Finds if the board contains word."""
    M = len(board)
    N = len(board[0])

    def backtrack(w, i, j):

        if not (0 <= i < M and 0 <= j < N) or board[i][j] == "#":
            return False

        if board[i][j] != word[w - 1]:
            return False

        if w == len(word):
            return True

        original = board[i][j]
        board[i][j] = "#"

        found = (
            backtrack(w + 1, i - 1, j)
            or backtrack(w + 1, i + 1, j)
            or backtrack(w + 1, i, j - 1)
            or backtrack(w + 1, i, j + 1)
        )

        board[i][j] = original
        return found

    for i in range(M):
        for j in range(N):
            if board[i][j] == word[0] and backtrack(1, i, j):
                return True

    return False

Test

>>> from word_search__backtracking import exist
>>> exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED")
True
>>> exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE")
True
>>> exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB")
False

Complexity

\(m \times n\) is the size of the board, and \(l\) is the length of the word.

Measure	Complexity	Notes
Time	\(O(mn \cdot 4^l)\)	worst case we find the word at the end of the board
Auxiliary Space	\(O(l)\)	recursive call stack

word_search__backtracking.exist(board: list[list[str]], word: str) → bool

Finds if the board contains word.