Word Search — LeetCode 79 Python Solution

The problem

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.

Example

Input

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

Output

true

Python solution

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i: int, j: int, k: int) -> bool:
            if k == len(word) - 1:
                return board[i][j] == word[k]
            if board[i][j] != word[k]:
                return False
            c = board[i][j]
            board[i][j] = "0"
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                x, y = i + a, j + b
                ok = 0 <= x < m and 0 <= y < n and board[x][y] != "0"
                if ok and dfs(x, y, k + 1):
                    return True
            board[i][j] = c
            return False

        m, n = len(board), len(board[0])
        return any(dfs(i, j, 0) for i in range(m) for j in range(n))

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 79. Word Search is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems