Given a board of characters and a list of dictionary words, return all words that can be formed by moving horizontally or vertically between adjacent cells. Pattern focus: Word Search with Trie (Multi-Word DFS). Trie pruning is the difference between a brute-force search and a scalable solution.
board = character grid, words = dictionary words
all matched words in lexicographic order
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]
Explanation:
Two dictionary words can be traced on the grid using four-directional movement.
Example 2:
Input:
board = [["a"]] words = ["b"]
Output:
[]
Explanation:
A single-cell board with a non-matching word returns no results.
Example 3:
Input:
board = [["a","b"],["c","d"]] words = ["ab","abcd","acdb"]
Output:
[ab,acdb]
Explanation:
Different words may share the same grid cells in different paths, as long as each cell is used once per word path.