Boggle - Find Possible Words
Filed under Amazon
Free read 3 of 3Confirm adjacency rules (horizontally and vertically adjacent) and whether a word can be matched multiple times.
The question
Given a 2D board and a dictionary of words, find all words that can be formed by a sequence of adjacent cells. Each cell can be used at most once in a single word.
Constraints
- board dimensions m x n up to 12x12
- dictionary contains up to 10^5 words
Examples
- 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"]
- Why
- Valid words found on the board using adjacent cells.
Approach
Confirm adjacency rules (horizontally and vertically adjacent) and whether a word can be matched multiple times.
Run DFS from every cell for every word in the dictionary, leading to massive redundant path checks.
Insert all dictionary words into a Trie. Traverse the board using DFS, matching paths against the Trie nodes to prune invalid prefixes early.
Single-character boards, empty dictionary, or boards smaller than the smallest word length.
Tips
- What they are testing: Test with boards containing repeated characters, overlapping words, and dictionaries with prefix overlaps.
- Common mistake: Failing to mark cells as visited during DFS, leading to infinite loops or invalid character reuse within the same word path.
Follow-ups
- What is the time complexity and working of a set?
- How to implement using a Trie?
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.