Katkat
Back

Find Words in a Character Grid

ByteDanceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates algorithm design for efficient multi-word search in a character grid, testing competencies in constrained graph traversal, managing large dictionaries, and selecting data structures for efficient lookup.

Implement findWords(board, words) for a word-search game.

You are given an m x n grid of lowercase English letters and a list of lowercase dictionary words. A word can be formed by starting at any cell and repeatedly moving one step up, down, left, or right. The same grid cell may not be used more than once in a single word.

Return all unique dictionary words that can be formed in the grid. The output order does not matter.

Constraints:

  • 1 <= m, n <= 12
  • 1 <= words.length <= 30000
  • 1 <= words[i].length <= 10
  • All words contain only lowercase English letters.

Optimize for a large dictionary and avoid searching the grid independently for every word.