The problem
Given an m × n grid of letters and a word, return true if the word can be traced on the grid: moving between cells that touch horizontally or vertically, one letter per cell, using no cell twice.
Examples
- Input
board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCCED"
- Output
true
- Input
board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "SEE"
- Output
true
- Input
board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCB"
- Output
false
Constraints
- 1 ≤ m, n ≤ 6
- 1 ≤ word.length ≤ 15
- Upper- and lowercase English letters only.
The idea
Try each cell as the start. From a cell holding the right letter, the next letter must be in one of its four neighbours: explore each, depth-first. If none works, this cell is a dead end — undo and return.
A cell on the current path is marked (overwritten with #) so the path cannot loop back through it, and unmarked on the way back so other paths can use it. Before any search, check the board has enough of each letter the word needs; if not, the answer is false at once.
- Time
- O(m · n · 4 · 3^(L−1)) — each start, 4 directions, then 3 new ones a step
- Space
- O(L) — the path, L the word’s length
Solution · every language run against every case
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: rows, cols = len(board), len(board[0]) # Quick refusal: the board must hold enough of every letter the word needs. if Counter(word) - Counter(c for row in board for c in row): return False def trace(r, c, i): # can word[i:] be traced starting at (r, c)? if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]: return False if i == len(word) - 1: return True board[r][c] = "#" # in use on this path found = trace(r + 1, c, i + 1) or trace(r - 1, c, i + 1) or trace(r, c + 1, i + 1) or trace(r, c - 1, i + 1) board[r][c] = word[i] # free it again return found return any(trace(r, c, 0) for r in range(rows) for c in range(cols))