Coding questions · ByteDance
Find Words in a Character Grid
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 <= 121 <= words.length <= 300001 <= 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.
Find Words in a Character Grid
Examples
Example 1
Input: ([['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']], ['oath','pea','eat','rain'])
Output: ['eat', 'oath']
Explanation: The words 'oath' and 'eat' can be formed by valid adjacent paths. 'pea' and 'rain' cannot.
Example 2
Input: ([['a']], ['a','aa','b','a'])
Output: ['a']
Explanation: Only 'a' can be formed. 'aa' would require reusing the same cell, and duplicates should appear only once in the result.
Hints
- Searching the full grid separately for every word repeats a lot of work. Think about a data structure that groups words by shared prefixes.
- While doing DFS from the board, stop exploring as soon as the current path is not a prefix of any remaining dictionary word.