Find all dictionary words in a grid
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given:
- A 2D grid of characters `board` with `m` rows and `n` columns.
- A list of strings `words` (a dictionary).
A word can be formed by starting from any cell and moving to **adjacent** cells (up, down, left, right). Each cell may be used **at most once** in forming a single word.
Return **all distinct** words from `words` that can be formed in the grid.
### Input
- `board`: `m x n` array of lowercase letters.
- `words`: list of lowercase strings.
### Output
- A list (or set) of all dictionary words that appear in the board.
### Constraints (reasonable interview constraints)
- `1 <= m, n <= 12`
- `1 <= len(words) <= 3 * 10^4`
- `1 <= len(word) <= 10`
- Letters are lowercase `a-z`.
### Notes
- The interviewer hinted that a **trie (prefix tree)** is a common approach, but a **backtracking** solution is also acceptable if performance is addressed.
Quick Answer: This question evaluates skills in grid traversal, string-search and pattern-matching techniques, recursive backtracking, and the efficient use of data structures for prefix-based lookup, along with time and space complexity reasoning.
Return sorted distinct dictionary words that can be formed by 4-directional backtracking without reusing a cell.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']], ['oath','pea','eat','rain'])
Expected Output: ['eat', 'oath']
Explanation: Classic word search.
Input: ([['a']], ['a','b'])
Expected Output: ['a']
Explanation: Single cell.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.