Word Search Matrix

Check whether a word appears in any of the four cardinal directions in a grid.

matrix dfs strings grid

Write a function `exists(board, word)` that takes a 2D list of characters `board` and a string `word`, and returns `True` if the `word` can be found in the grid by moving horizontally or vertically (up, down, left, or right) to adjacent cells, using each cell at most once. The function should return `False` otherwise.

The word can start at any cell. The path cannot visit the same cell twice. The grid may be empty, and the word may be empty (an empty word is considered found).

Constraints

- `1 <= len(board) <= 10`
- `1 <= len(board[0]) <= 10`
- `0 <= len(word) <= 100`
- Characters are lowercase English letters.

Time complexity should be O(R*C*3^L) in the worst case, with R and C the grid dimensions and L the word length.

Example

>>> board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
>>> exists(board, "ABCCED")
True
>>> exists(board, "SEE")
True
>>> exists(board, "ABCB")
False
>>> exists(board, [], "A")
False

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a recursive backtracking function that tries each cell as a starting point.

Mark visited cells (e.g., temporarily change the character) to avoid reusing cells.

If the word is empty, the function should return True.

Handle an empty board (no rows) and empty word cases first.

Test Results

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