Find Which Words From a List Can Be Traced Through Adjacent Cells of a Letter Grid
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an `m x n` grid of lowercase letters and a list of words. A word can be traced in the grid if there is a sequence of cells whose letters spell the word in order, where each cell is horizontally or vertically adjacent to the previous one and no cell is used twice within that word.
Return every word from the list that can be traced in the grid.
The interview started with the single-word version (decide whether one given word can be traced), and the follow-up asked for a whole list of words at once. A list containing one word is the single-word version.
### Function Signature
```python
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
```
### Rules
- Adjacent means sharing an edge: up, down, left or right. Diagonal cells are not adjacent.
- A cell may appear at most once in the path of one word. Different words may reuse the same cells.
- A word that appears more than once in `words` appears at most once in the output.
- Return the traceable words sorted in ascending lexicographic order, or an empty list if none can be traced.
### Constraints
- `1 <= m, n <= 12`, where `m = len(board)` and `n = len(board[i])` for every row `i`
- Every `board[i][j]` is a single lowercase English letter.
- `1 <= len(words) <= 30000`
- `1 <= len(words[i]) <= 10`, and every word consists of lowercase English letters.
### Examples
**Example 1**
```text
Input: board = [
["c", "a", "t"],
["r", "o", "s"],
["e", "d", "g"]
]
words = ["cat", "cot", "rod", "red", "dog", "oat"]
Output: ["cat", "oat", "red", "rod"]
```
`"cot"` fails because `c` at `(0, 0)` and `o` at `(1, 1)` are only diagonal neighbours. `"dog"` fails because the `g` at `(2, 2)` is not adjacent to the only `o`, at `(1, 1)`.
**Example 2**
```text
Input: board = [
["a", "b"],
["c", "d"]
]
words = ["abdc", "aba", "abcd", "a", "a"]
Output: ["a", "abdc"]
```
`"aba"` would need the single `a` cell twice. `"abcd"` needs `b` at `(0, 1)` followed by `c` at `(1, 0)`, which are diagonal. `"a"` is listed twice but returned once.
**Example 3**
```text
Input: board = [["a", "a"]]
words = ["aaa"]
Output: []
```
The grid has only two `a` cells, and a cell cannot be reused within one word.
Overview: Given a letter grid and a list of words, return every word that can be spelled by a path of edge-adjacent cells without reusing a cell, sorted lexicographically. Covers the single-word search and its many-words follow-up, and tests backtracking and pruning on a large word list.
You are given an `m x n` grid `board` of lowercase English letters and a list of strings `words`. A word can be **traced** in the grid if there is a sequence of cells whose letters spell the word in order, where each cell is horizontally or vertically adjacent to the previous one and no cell is used twice within that word.
Return every word from `words` that can be traced in the grid.
This is the list version of the single-word question "can this one word be traced?": a `words` list containing one word is exactly the single-word version.
### Rules
- Adjacent means sharing an edge: up, down, left or right. Diagonal cells are not adjacent.
- A cell may appear at most once in the path of one word. Different words may reuse the same cells.
- `words` may contain duplicates. A word that appears more than once in `words` appears at most once in the output.
- Return the traceable words sorted in ascending lexicographic order, or an empty list if none can be traced.
### Function Signature
```python
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
```
Each `board[i][j]` is passed as a one-character string. Every input and output value is a letter or a string; there are no numeric values, so nothing can exceed 2^31 - 1.
### Constraints
- `1 <= m, n <= 12`, where `m = len(board)` and `n = len(board[i])` for every row `i`
- Every `board[i][j]` is a single lowercase English letter.
- `1 <= len(words) <= 30000`
- `1 <= len(words[i]) <= 10`, and every word consists of lowercase English letters.
### Example 1
```text
Input: board = [
["c", "a", "t"],
["r", "o", "s"],
["e", "d", "g"]
]
words = ["cat", "cot", "rod", "red", "dog", "oat"]
Output: ["cat", "oat", "red", "rod"]
```
`"cot"` fails because `c` at `(0, 0)` and `o` at `(1, 1)` are only diagonal neighbours. `"dog"` fails because the `g` at `(2, 2)` is not adjacent to the only `o`, at `(1, 1)`. The traceable words are returned in sorted order, not input order.
### Example 2
```text
Input: board = [
["a", "b"],
["c", "d"]
]
words = ["abdc", "aba", "abcd", "a", "a"]
Output: ["a", "abdc"]
```
`"aba"` would need the single `a` cell twice. `"abcd"` needs `b` at `(0, 1)` followed by `c` at `(1, 0)`, which are diagonal. `"a"` is listed twice but returned once.
Constraints
- 1 <= m, n <= 12, where m = len(board) and n = len(board[i]) for every row i
- Every board[i][j] is a single lowercase English letter.
- 1 <= len(words) <= 30000
- 1 <= len(words[i]) <= 10, and every word consists of lowercase English letters.
Examples
Input: ([['c', 'a', 't'], ['r', 'o', 's'], ['e', 'd', 'g']], ['cat', 'cot', 'rod', 'red', 'dog', 'oat'])
Expected Output: ['cat', 'oat', 'red', 'rod']
Explanation: Source Example 1: 'cot' needs a diagonal step and 'dog' has no o next to g; the four traceable words are sorted, not in input order.
Input: ([['a', 'b'], ['c', 'd']], ['abdc', 'aba', 'abcd', 'a', 'a'])
Expected Output: ['a', 'abdc']
Explanation: Source Example 2: 'aba' would reuse the only a, 'abcd' needs the diagonal b-c step, and the duplicated 'a' is returned once.
Hints
- Settle the single-word question first: what must hold between consecutive cells of a path that spells the word, and how do you guarantee no cell appears twice in it?
- Words in the list can share their opening letters, and one word can be a prefix of another; a path that spells a shorter word may continue into a longer one.
- The output contains each traceable word once, in ascending lexicographic order, no matter how often or where it appears in words.