You are given a 2D grid `board` of lowercase English letters with `m` rows and `n` columns. A **word** can be constructed from letters of sequentially adjacent cells, where *adjacent* cells are horizontally or vertically neighboring (no diagonals). The **same grid cell may not be used more than once** within a single word. This question has two parts that build on each other: first matching a single word, then efficiently matching a large dictionary of words against the same board. ### Constraints & Assumptions - `1 <= m, n <= 12` for Part 1; for Part 2 the board can be larger (up to roughly `12 x 12`), and the word list can hold up to `~3 * 10^4` words. - Each word has length up to `~10` characters and consists of lowercase English letters `a`–`z`. - The board and words contain only lowercase English letters. - A cell, once consumed in the current path, cannot be revisited *in that same path*, but is freely available again when you start a new path or backtrack. - The word list may contain duplicates; the result should not. ### Clarifying Questions to Ask - Are diagonal moves allowed, or only the 4 orthogonal directions? (Assume orthogonal only.) - Can a single board cell be reused within one word's path? (No — each cell at most once per word.) - For Part 2, can the same board cell be reused *across* different words? (Yes — each word is matched independently.) - Should the returned words preserve input order, dedupe duplicates, and what is expected for the empty grid or empty word list? - What are the realistic upper bounds on board size, word count, and word length? (This drives whether the brute-force-per-word approach in Part 1 is acceptable at scale.) ### Part 1 Given a single target `word`, determine whether `word` can be formed by a path in the board under the adjacency and no-reuse rules above. Return a boolean. ```hint Where to start This is a search over paths in a grid. Try a depth-first search (backtracking) launched from every cell whose letter equals `word[0]`, walking to the 4 neighbors that match the next character. ``` ```hint Tracking visited cells You need to avoid reusing a cell within the current path. Either keep a separate `visited` matrix, or mutate the board cell in place to a sentinel (e.g. `#`) before recursing and restore it on backtrack — that avoids extra space. ``` ```hint Pruning and complexity Prune as early as possible: bail the moment a letter mismatches or you step off the board. The worst-case time is roughly $O(m \cdot n \cdot 4^{L})$ where $L$ is the word length (4 directions per step, minus the cell you came from), and recursion depth is $O(L)$. ``` #### What This Part Should Cover - A correct backtracking DFS that starts from every viable origin cell and respects the 4-directional adjacency. - Correct, restored visited-state on backtrack (no leaked mutations to the board). - Stated time/space complexity in terms of board size and word length, with the branching-factor reasoning. ### Part 2 As a follow-up, you are given a **list of words** `words`. Return **all distinct words** from the list that can be formed on the board under the same adjacency and no-reuse rules. The list can be large and many words share common prefixes, so design for that — running Part 1 independently for every word is too slow. ```hint Where to start Re-running the Part 1 DFS once per word re-walks shared prefixes again and again. Index the *dictionary* into a structure that lets one board traversal match many words at once. ``` ```hint Data structure Build a **trie (prefix tree)** from `words`. Then DFS the board once, advancing a trie pointer in lockstep with the path: only continue into a neighbor if the trie has a child for that letter. A node marked as a word-end means you've matched a full word — record it. ``` ```hint Making it fast and avoiding duplicates Store the full word at the trie's terminal node so you can add it directly to a result set on a hit. Two key optimizations: (1) after collecting a word, set its terminal flag to `None`/false so it isn't reported twice; (2) **prune the trie** — remove leaf nodes with no children after a match so dead branches stop being explored. This bounds work by what's still reachable rather than the whole dictionary. ``` #### What This Part Should Cover - A trie built from the word list, with each terminal node carrying the matched word (or enough to reconstruct it). - A single board DFS that advances board position and trie pointer together, only recursing where the trie has a matching child. - Deduplication of results and a correctness argument that one traversal covers all words sharing a prefix. - Complexity discussion: trie build cost, and why the board DFS bound depends on the trie/branching rather than `words.length × per-word DFS`. ### What a Strong Answer Covers Across both parts, a strong answer demonstrates the same core grid-search skill scaling from one word to many: - Recognizing Part 2 as a generalization of Part 1, and *why* a per-word loop is wasteful when prefixes are shared (the trie collapses shared prefix work). - Clean handling of the shared edge cases: empty board, empty word list, duplicate words, words longer than `m × n` (impossible — can prune), and words containing letters absent from the board. - Honest complexity analysis for both parts, including the exponential branching factor of grid DFS and how trie pruning tightens the practical bound. - Correct visited/backtracking discipline so no state leaks between paths or words. ### Follow-up Questions - In Part 2, how does pruning the trie (removing matched/leaf nodes) change the worst-case versus the practical running time? - If the board were extremely large but the dictionary small, would you still prefer the trie approach, or index the board instead (e.g. precompute letter positions)? - How would you parallelize Part 2 across many starting cells or many board regions, and what shared state would need synchronization? - Suppose words could reuse a cell (no no-reuse constraint) and had bounded length — how would the search and complexity change?