Word Search in a Letter Grid
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Word Search in a Letter Grid
Given an `m x n` grid of lowercase letters and a list of target words, return every target word that can be constructed from letters of **sequentially adjacent** cells, where adjacent cells are horizontal or vertical neighbors. Within a single word, the same grid cell may not be used more than once. Each word in the result should appear at most once; return the results sorted in ascending lexicographic order.
This is the many-words variant — the word list can be large, so a naive independent search per word will be too slow. Build a prefix structure over the words so that a single traversal of the grid can prune branches that cannot extend any remaining word.
## Input
- `board`: `List[str]`, where each string is one row of the grid (all rows the same length). `1 <= m, n <= 12`.
- `words`: `List[str]`, `1 <= len(words) <= 3 * 10^4`, each word of length `1 <= L <= 12`, lowercase letters only. Words may share prefixes; the list may contain duplicates (the output must not).
## Output
- `List[str]`: the distinct words found in the board, sorted ascending.
## Example
Input:
```
board = ["oaan",
"etae",
"ihkr",
"iflv"]
words = ["oath", "pea", "eat", "rain", "hklf", "hf"]
```
Output:
```
["eat", "hf", "hklf", "oath"]
```
Explanation: `oath`, `eat`, `hklf`, and `hf` can each be traced along adjacent cells without reusing a cell; `pea` and `rain` cannot.
Quick Answer: This question evaluates a candidate's ability to search for multiple target words within a grid of letters using depth-first traversal and backtracking. It commonly tests trie construction to efficiently prune search paths when many words must be matched simultaneously, assessing practical algorithm design under scale constraints in coding interviews.
Given an `m x n` grid of lowercase letters (`board`, each string is one row) and a list of target words (`words`), return every target word that can be constructed from letters of **sequentially adjacent** cells, where adjacent cells are horizontal or vertical neighbors (4-directional). Within a single word, the same grid cell may not be used more than once. Each word in the result should appear at most once; return the results sorted in ascending lexicographic order.
This is the many-words variant — the word list can be large (up to `3 * 10^4`), so a naive independent search per word is too slow. Build a prefix trie over the words so that a single DFS traversal of the grid prunes any branch whose accumulated path is not a prefix of some remaining word.
## Constraints
- `board`: `1 <= m, n <= 12`, all rows the same length, lowercase letters.
- `words`: `1 <= len(words) <= 3 * 10^4`, each word length `1 <= L <= 12`, lowercase letters. Words may share prefixes and may contain duplicates (the output must not).
## Example
Input: `board = ["oaan","etae","ihkr","iflv"]`, `words = ["oath","pea","eat","rain","hklf","hf"]`
Output: `["eat","hf","hklf","oath"]`
`oath`, `eat`, `hklf`, and `hf` can each be traced along adjacent cells without reusing a cell; `pea` and `rain` cannot.
Constraints
- 1 <= m, n <= 12; all rows of board have equal length; lowercase letters only.
- 1 <= len(words) <= 3 * 10^4; each word length 1 <= L <= 12; lowercase letters.
- Adjacent cells are 4-directional (horizontal/vertical) neighbors only.
- A single grid cell may not be reused within one word.
- Duplicate input words allowed; each found word appears at most once in the output.
- Output must be sorted in ascending lexicographic order.
Examples
Input: (['oaan', 'etae', 'ihkr', 'iflv'], ['oath', 'pea', 'eat', 'rain', 'hklf', 'hf'])
Expected Output: ['eat', 'hf', 'hklf', 'oath']
Explanation: oath (o->a->t->h), eat (e->a->t), hklf (h->k->l->f), and hf (h->f) all trace along adjacent unused cells; pea has no 'p' and rain cannot be traced.
Input: (['a'], ['a'])
Expected Output: ['a']
Explanation: Single-cell grid, single-letter word matches the one cell.
Input: (['ab', 'cd'], ['xyz'])
Expected Output: []
Explanation: No target word can be formed from the grid letters.
Input: (['ab'], ['ab', 'ab', 'ba'])
Expected Output: ['ab', 'ba']
Explanation: Duplicates collapse to one; both 'ab' (a->b) and 'ba' (b->a) are traceable on the two adjacent cells.
Input: (['ab'], ['aba'])
Expected Output: []
Explanation: 'aba' would require reusing the 'a' cell, which is not allowed.
Input: (['ab'], ['a', 'ab'])
Expected Output: ['a', 'ab']
Explanation: A word that is a prefix of another is still reported when its own end-of-word marker is reached.
Hints
- Insert all (deduplicated) words into a trie. During DFS from each cell, walk down the trie in lockstep with the path; if the current letter is not a child of the trie node, prune the whole branch.
- Mark a cell as visited (e.g. overwrite with a sentinel) before recursing into its 4 neighbors, then restore it on backtrack so it can be reused by other words.
- When the trie node reached carries an end-of-word marker, add that word to a result set (a set naturally handles the same word being reachable via multiple paths). Return sorted(result).