Determine whether a word exists in a letter grid

Problem Statement

Given an m x n grid of characters board and a string word, return True if word exists in the grid, or False otherwise.

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 in a single word path.

Function Signature

def exist(board: list[list[str]], word: str) -> bool:
    pass

Input and Output Format

• Input:
  • board: A list of lists of strings, where each element is a single character.
  • word: A string consisting of English letters.
• Output: A boolean (True or False).

Constraints

• m == len(board)
• n == len(board[i])
• 1 <= m, n <= 6
• 1 <= len(word) <= 15
• board and word consist of only lowercase and uppercase English letters.

Examples

Example 1

board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
]
word = "ABCCED"
# Output: True

Explanation: The path board[0][0] -> board[0][1] -> board[0][2] -> board[1][2] -> board[2][2] -> board[2][1] spells "ABCCED".

Example 2

board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
]
word = "ABCB"
# Output: False

Explanation: The cell 'B' at (0, 1) cannot be reused to form the second 'B'.

Edge Cases to Consider

• len(word) > m * n: Word length exceeds total available characters in the grid (immediate False).
• m == 1 and n == 1: Grid contains a single cell.
• A word with repeated identical characters where backtracking must properly restore visited state.