Find Which Words From a List Can Be Traced Through Adjacent Cells of a Letter Grid

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.