Word Search
Decide whether a word can be traced through horizontally or vertically adjacent cells of a letter grid, using each cell at most once.
A way to picture it
A rock climber follows a route of handholds spelling a word. At each hold they try the four directions for the next letter. Hit a dead end and they climb back down one hold, freeing it up, and try another way.
How to approach it
DFS from every cell that matches the first letter. Mark cells as used on the way in, and unmark them on the way back out (backtracking).
Example
Input: {"board":[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"word":"ABCCED"}. Output: true.
Complexity: O(cells ยท 3^L) time and O(L) space. After the first step, each move has at most 3 unused directions; recursion depth is the word length.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.