Katkat
Back

Find all dictionary words in a grid

UberSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate a 2D grid using backtracking and optimize dictionary lookups using a Trie data structure.

Problem Statement

Given a 2D grid of characters and a dictionary of valid words, find all words from the dictionary that can be formed by a sequence of adjacent cells (horizontally or vertically). Each cell in the grid can be used at most once for a single word.

Implement the following function: def find_words(grid, words) -> List[str]

Constraints

  • grid dimensions: M x N, where 1 <= M, N <= 10.
  • words list length: Up to 1000 words.
  • Word length: Up to 10 characters.

Examples

Example 1: Input:

grid = [['a', 'b'], ['c', 'd']]
words = ['ab', 'ad', 'ac']

Output: ['ab', 'ac', 'ad']

Example 2: Input:

grid = [['a', 'e'], ['f', 'g']]
words = ['aeg', 'af']

Output: ['aeg', 'af']

Edge Cases

  • Empty grid or empty dictionary.
  • Words that share the same prefix in the grid.
  • Words that require backtracking to the same cell (not allowed).

Implementation Note

While a basic DFS approach works, consider how to avoid redundant searches for words sharing prefixes.

Hints

Hint 1

Use a Trie to store the dictionary, allowing you to prune search paths that do not form a valid prefix.

Hint 2

Perform a Depth First Search (DFS) starting from every cell in the grid, marking visited cells to ensure each word sequence is valid.

Hint 3

Include a 'visited' set or modify the grid in-place (e.g., replace character with '#') during recursion to prevent re-using the same cell in a single word path.

Follow-up questions

  • How would you modify your solution to return the words found if the grid allowed moving diagonally as well?
  • If the grid were extremely large, how would the performance change, and what optimizations could you suggest?
  • How does the time complexity change if you use a Trie versus checking every word against the grid independently?