Word Search Backtrack

Explore a grid to find if a word can be formed by adjacent cells without revisiting.

backtracking matrix dfs recursion strings

Write a function `exists(board, word)` that returns `True` if the `word` can be constructed from letters of sequentially adjacent cells in the `board`. Adjacent cells are horizontally or vertically neighboring (not diagonal). The same cell may not be used more than once while constructing the word.

- `board` is a list of strings, each string of the same length (uppercase and lowercase letters).
- `word` is a non-empty string.
- The function must look for the entire word as a contiguous path on the board.

Return `True` if the word exists, otherwise `False`.

Constraints

1 <= len(board) <= 10, 1 <= len(board[0]) <= 10, 1 <= len(word) <= 20. Assume board[0] exists.

Example

>>> exists(["ABCE", "SFCS", "ADEE"], "ABCCED")
True
>>> exists(["ABCE", "SFCS", "ADEE"], "SEE")
True
>>> exists(["ABCE", "SFCS", "ADEE"], "ABCB")
False

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start a search from every cell that matches the first character of the word.

Use a helper that explores up, down, left, right while keeping track of the current index and visited cells.

When a path fails, backtrack by unmarking the cell so other paths can reuse it.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.