Grid Word Hunt
HardTries & Strings
Problem
A letter grid is given as board, a list of equal-length rows. A word can be traced on the grid by starting at any cell and repeatedly stepping to a horizontally or vertically adjacent cell; a cell may be used at most once within the same word.
Given a list of distinct words, return all of them that can be traced. The order of the result does not matter.
Example 1
- Input:
- board = ["cat","ore","bed"], words = ["cat","care","bed","rob","tea","core","dart"]
- Output:
- ["cat","care","bed","rob","core"]
"tea" fails because the e next to t has no neighbouring a; "dart" fails because d has no neighbouring a.
Example 2
- Input:
- board = ["ab","cd"], words = ["abdc","abcd","acdb","ad"]
- Output:
- ["abdc","acdb"]
Diagonal steps are not allowed, so b → c and a → d are impossible.
Constraints
- 1 ≤ rows, columns ≤ 12
- 1 ≤ words.length ≤ 3·10^4
- 1 ≤ words[i].length ≤ 10
- Lowercase English letters; words are distinct.
Hint
Show the first hint
Searching the grid once per word repeats the same paths for words with common beginnings.
Walkthrough
How to approach it
01Clarify before coding
- Diagonal moves? No, only up, down, left and right.
- Can a cell be reused in one word? No; it can be reused across different words.
- Should a word be reported twice if it can be traced two ways? No, each word at most once.
02Brute force
For each word, run a separate backtracking search from every cell.
Cost: O(W·R·C·4·3^(L-1)): 3·10^4 words on a 12×12 grid repeat almost the same exploration thousands of times.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.