Where it runs
1. The problem
You have a grid of letters and one word. Can you spell the word by walking the grid one cell at a time? You may move only up, down, left or right, never diagonally. You may not step on the same cell twice. Answer yes or no.
The hard part is that one letter can sit in many places, so there are many paths to check. You need a way to try a path and, when it hits a dead end, step back and try another one.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedexist([["C", "A", "T", "S"], ["A", "X", "T", "O"], ["T", "O", "P", "S"]], "TOP")| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | C | A | T | S |
| 1 | A | X | T | O |
| 2 | T | O | P | S |
Does "TOP" appear as a path of neighbouring cells, each used once? Try a start from every cell in turn.
Recognise it
Say these words and it is this pattern
- does the word exist as a path on the board
- trace letters through adjacent cells, no reuse
- DFS with backtracking on a grid
- mark a cell as visited, then undo it
Looks similar, isn't
- Backtracking
This is backtracking with the grid as the tree. The choices are the four neighbours.
- Graph BFS / DFS
A traversal marks a cell once and forever. Here the mark comes off on the way out.
- Connected components
Flood fill also walks neighbours, but it never unmarks. It is counting rather than searching.
- Trie (prefix tree)
With many words to find, a trie prunes the walk. Without one each word costs its own search.
An r by c grid with a word of length L costs O(rc times 4L). Pruning is what makes it run.
On LeetCode
Grid problems that look for a path through neighbouring cells without reusing a cell, such as spelling a word or collecting the most gold. A DFS marks the cell, tries the four neighbours and puts the cell back on the way out.
The lesson task, word for word.
Start the same DFS from every cell with gold and keep the best total. At most 25 cells hold gold, so this passes.
Count the empty cells first, and a path counts only when it reaches the end after stepping on all of them.
Put the words in a trie from lesson 129, run one DFS per cell that follows the trie, and cut each found word out as in lesson 130 so the search ends sooner.