hardTriesPure DSA~36 min
Keyword Grid Multi-Search
A moderation system scans a grid of characters for any of a watchlist of keywords, where a match is a path of adjacent cells. Return every watchlist word that appears.
Problem
Given an m × n board of characters and a list of words, return all words that can be constructed from sequentially adjacent (horizontally or vertically) cells, where each cell is used at most once per word.
Input
A board of size m × n (1 ≤ m, n ≤ 12) and words (1 ≤ count ≤ 3·10^4), each up to length 10.
Output
A list of the matching words, in any order, without duplicates.
Constraints
- A single cell cannot be reused within one word's path
- Lowercase English letters only
- Up to 30,000 words — a Trie is required, per-word DFS is too slow
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
["oath","eat"]
'oath' and 'eat' trace adjacent paths; 'pea' and 'rain' do not.
Example 2
Input
board = [["a","b"],["c","d"]], words = ["abcb"]
Output
[]
'abcb' would reuse 'b', which is not allowed.