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.
