Given a grid of letters and a word, return true if the word can be traced through the grid. Each step goes to a neighbour up, down, left or right, and a cell cannot be used twice.
DSA Animator › DSA Revision › Matrix › Word Search
Remember: DFS plus mark and unmark is backtracking on a grid. Stop early as soon as a letter does not match. The video solves Word Search (LeetCode 79, Medium) with the Backtracking DFS pattern from the Matrix topic, and you can replay every step in the interactive Word Search animation.
Given a grid of letters and a word, return true if the word can be traced through the grid. Each step goes to a neighbour up, down, left or right, and a cell cannot be used twice.
For this grid, the word A B C C E D can be traced, so the answer is true.
Listing every path in the grid is exponential and wasteful. We only need to follow paths that keep matching the word.
Try each cell as a starting point. From a cell that matches the current letter, explore its four neighbours for the next letter. Mark the cell as used while exploring, and unmark it when you come back, which is backtracking.
Start at A in the top left, which matches the first letter. Its right neighbour is B, the second letter. Then C to the right. The next letter is C again, found below. Then E below that. Finally D, to the left. All six letters matched, so the answer is true.
In code, call DFS from every cell with letter index 0. DFS returns true when the index reaches the end of the word, and false when it leaves the grid or the letter does not match. Otherwise it marks the cell, tries the four neighbours with the next index, and restores the cell. In the worst case it's O of m times n times 3 to the power L, where L is the word length.
Remember: DFS plus mark and unmark is backtracking on a grid. Stop early as soon as a letter does not match.