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

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

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

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

Input:  board = [["a", "a"]]
words = ["aaa"]
Output: []

The grid has only two a cells, and a cell cannot be reused within one word.

Trace Words Through a Letter Grid

Hints

1. 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?
2. 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.
3. The output contains each traceable word once, in ascending lexicographic order, no matter how often or where it appears in words.

Approach

Build a prefix tree (trie) over all words; the node where a word ends stores that word. Then run a backtracking depth-first search from every cell, carrying the trie node that corresponds to the letters of the current path. A step into a neighbouring cell is taken only if the cell is inside the grid, shares an edge with the current cell (up, down, left, right; never diagonal), is not already on the current path, and its letter is a child of the current trie node. The cell is marked as on-path while its subtree is explored and unmarked on the way back, so different words and different branches can reuse cells while a single path never repeats one.

Invariant: the search sits at trie node T exactly when the current self-avoiding, edge-adjacent path spells T's prefix. Therefore a word is recorded precisely when some valid path spells it, which is the definition of traceable, and every traceable word is reached because every valid path whose letters stay inside the trie is explored. When a word is recorded its marker is cleared; all copies of a duplicated word end at the same node, so each word is output once. After a node's subtree is exhausted, a node with no remaining word marker and no children is removed from its parent: it can no longer lead to an unrecorded word, so removing it never loses an answer but stops re-exploring finished prefixes. The outer loop stops starting searches once the root has no children.

Finally the recorded words are sorted in ascending lexicographic order. All characters are lowercase ASCII letters, so ordinary string comparison in Python, JavaScript, Java and C++ gives exactly that order, with a proper prefix sorting before its extensions.

Edge cases: a word longer than m*n can never be traced because it would need a repeated cell; a word containing a letter missing from the grid never matches; if nothing can be traced the result is an empty list. The recursion depth is at most the maximum word length, 10.

• Time complexity: O(WL + mn43^(L-1) + KLlog K), where W = len(words), L <= 10 is the maximum word length and K is the number of words returned
• Space complexity: O(WL + mn)