Katkat
Back

Word Search in a Letter Grid

AnthropicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to implement a backtracking search on a 2D grid, optimized with a Trie data structure to efficiently search for multiple strings simultaneously.

Problem Statement

Given an m x n grid of characters and a list of strings words, return all words from the list that can be found in the grid.

A word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Function Signature

def findWords(board: List[List[str]], words: List[str]) -> List[str]:

Constraints

  • m == board.length, n == board[i].length
  • 1 <= m, n <= 12
  • 1 <= words.length <= 3 * 10^4
  • 1 <= words[i].length <= 10
  • board and words consist of lowercase English letters.

Examples

Example 1: Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["eat","oath"]

Example 2: Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []

Edge Cases

  • The grid contains fewer letters than the word.
  • Multiple words share the same prefix.
  • The grid contains only one cell.

Hints

Hint 1

Using a simple DFS for every word will be inefficient; consider storing the target words in a Trie to prune the search space early.

Hint 2

During your backtracking, track the current path by temporarily modifying the board grid (e.g., changing a visited character to '#') and restoring it afterwards.

Hint 3

To avoid duplicate results in the output, you can either use a set to store found words or remove the word from the Trie once it has been matched.

Follow-up questions

  • How would your approach change if you were allowed to use the same cell multiple times within a single word?
  • What is the time complexity of your solution in terms of the number of cells in the grid and the total number of characters in the word list?
  • How would you optimize the solution if the grid were distributed across multiple machines in a cluster?