Find Every Listed Word That Can Be Traced Through Adjacent Cells of a Letter Grid
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a grid of lowercase letters and a list of words, return every word from the list that can be traced through the grid. A word is traced by starting at any cell and repeatedly stepping to a horizontally or vertically adjacent cell, so that the letters of the visited cells spell the word in order. Within one word, no cell may be visited twice.
The reported interview first asked whether a single word can be traced and then, as a follow-up, how to search for many words at once. This version asks for the many-word form; checking one word is the case where `words` has a single element.
### Function Signature
```python
def find_traceable_words(board: list[list[str]], words: list[str]) -> list[str]:
```
### Rules
- `board[r][c]` is a single lowercase letter. Cells `(r, c)` and `(r2, c2)` are adjacent exactly when `abs(r - r2) + abs(c - c2) == 1`; diagonal cells are not adjacent, and paths do not wrap around the edges of the grid.
- A word is traceable when some sequence of pairwise distinct cells, each adjacent to the next, has letters that read exactly the word.
- Each word is checked on its own: a cell used to trace one word may be used again for a different word.
- `words` may contain duplicates. Each traceable word appears once in the result.
- Return the traceable words in ascending lexicographic order (Python's default string ordering). Return an empty list when no word is traceable.
### Constraints
- `1 <= m, n <= 12`, where `m = len(board)` and `n = len(board[0])`; every row has length `n`.
- `1 <= len(words) <= 10^4`
- `1 <= len(words[i]) <= 10`
- Every board cell and every word contains only the lowercase English letters `a` to `z`.
### Examples
**Example 1**
```text
Input: board = [["c","a","t"],
["o","r","s"],
["d","o","g"]]
words = ["rats"]
Output: ["rats"]
```
The path is `r (1,1) -> a (0,1) -> t (0,2) -> s (1,2)`; every step moves one row or one column.
**Example 2**
```text
Input: board = [["c","a","t"],
["o","r","s"],
["d","o","g"]]
words = ["dog", "cart", "star", "tat", "cod", "dog"]
Output: ["cod", "dog", "star"]
```
`cod` is `c (0,0) -> o (1,0) -> d (2,0)`; `dog` is `d (2,0) -> o (2,1) -> g (2,2)` and appears once although it is listed twice; `star` is `s (1,2) -> t (0,2) -> a (0,1) -> r (1,1)`. `cart` is not traceable: the only `r`, at `(1,1)`, has no adjacent `t`, because `(0,2)` is diagonal to it. `tat` would have to visit the only `t` twice.
**Example 3**
```text
Input: board = [["a"]]
words = ["aa", "a"]
Output: ["a"]
```
`aa` would have to use the single cell twice.
Overview: A grid word-search coding problem: given a board of lowercase letters and a list of words, return in sorted order every word that can be spelled along a path of horizontally or vertically adjacent cells without reusing a cell. It tests backtracking search and handling many words efficiently at once.
Read the full Amazon Software Engineer interview experience this question came from
Given an `m x n` grid `board` of lowercase letters and a list of strings `words`, return every word from `words` that can be traced through the grid. A word is traced by starting at any cell and repeatedly stepping to a horizontally or vertically adjacent cell, so that the letters of the visited cells spell the word in order. Within one word, no cell may be visited twice.
This is the many-word form of the question "can one word be traced?": checking a single word is the case where `words` has one element.
### Rules
- `board[r][c]` is a single lowercase letter. Cells `(r, c)` and `(r2, c2)` are adjacent exactly when `abs(r - r2) + abs(c - c2) == 1`; diagonal cells are not adjacent, and paths do not wrap around the edges of the grid.
- A word is traceable when some sequence of pairwise distinct cells, each adjacent to the next, has letters that read exactly the word.
- Each word is checked on its own: a cell used to trace one word may be used again for a different word.
- `words` may contain duplicates. Each traceable word appears once in the result.
- Return the traceable words in ascending lexicographic order (Python's default string ordering, so a word comes before any longer word that begins with it). Return an empty list when no word is traceable.
### Function Signature
```python
def find_traceable_words(board: list[list[str]], words: list[str]) -> list[str]:
```
### Constraints
- `1 <= m, n <= 12`, where `m = len(board)` and `n = len(board[0])`; every row has length `n`.
- `1 <= len(words) <= 10^4`
- `1 <= len(words[i]) <= 10`
- Every board cell and every word contains only the lowercase English letters `a` to `z`.
No value in the input or output comes anywhere near 2^31 - 1; 32-bit integers suffice in every language.
### Examples
**Example 1**
```text
Input: board = [["c","a","t"],
["o","r","s"],
["d","o","g"]]
words = ["dog", "cart", "star", "tat", "cod", "dog"]
Output: ["cod", "dog", "star"]
```
`cod` is `c (0,0) -> o (1,0) -> d (2,0)`; `dog` is `d (2,0) -> o (2,1) -> g (2,2)` and appears once although it is listed twice; `star` is `s (1,2) -> t (0,2) -> a (0,1) -> r (1,1)`. `cart` is not traceable: the only `r`, at `(1,1)`, has no adjacent `t`, because `(0,2)` is diagonal to it. `tat` would have to visit the only `t` twice.
**Example 2**
```text
Input: board = [["a"]]
words = ["aa", "a"]
Output: ["a"]
```
`aa` would have to use the single cell twice.
Constraints
- 1 <= m, n <= 12, where m = len(board) and n = len(board[0]); every row has length n.
- 1 <= len(words) <= 10^4
- 1 <= len(words[i]) <= 10
- Every board cell and every word contains only the lowercase English letters a to z.
Examples
Input: ([['c', 'a', 't'], ['o', 'r', 's'], ['d', 'o', 'g']], ['rats'])
Expected Output: ['rats']
Explanation: Source Example 1, single-word query: r(1,1) -> a(0,1) -> t(0,2) -> s(1,2).
Input: ([['c', 'a', 't'], ['o', 'r', 's'], ['d', 'o', 'g']], ['dog', 'cart', 'star', 'tat', 'cod', 'dog'])
Expected Output: ['cod', 'dog', 'star']
Explanation: Source Example 2: cod, dog, star trace; cart needs the diagonal r-t step, tat reuses the only t, duplicate dog reported once.
Hints
- Two cells are neighbours only when they share an edge: one step changes the row or the column by exactly one, never both, and a path never wraps around the border.
- The no-reuse rule applies within one word only: every word is checked against a fresh board, and a word listed twice is still reported once.
- Words are at most 10 letters long but there can be 10^4 of them, and many may begin with the same letters; the follow-up asks you to search for all of them at once rather than one at a time.