Word Search Collection
Given a grid of letters and a list of words, return all words from the list that can be formed in the grid.
Words can be formed by connecting adjacent letters horizontally or vertically, not diagonally.
Each cell in the grid can only be used once per word.
Example Grid:
[['d', 'o', 'g', 's'],
['c', 'a', 't', 'p'],
['b', 't', 'a', 'r'],
['h', 'e', 'n', 's']
]Word List: [“cats”, “dog”, “hen”, “star”, “tap”, “rat”, “spa”, “net”]
Expected Output: [“dog”, “hen”, “rat”, “net”]
Write a function findWords(grid, wordList) that returns an array of all words from wordList found in the grid.
This is a classic multi-word search problem. The standard solution is to build a trie from the word list and then run DFS/backtracking from each grid cell, moving only up, down, left, and right. The trie helps prune dead paths early, which is much faster than checking every word one by one. In the example, words like dog, hen, rat, and net can be formed, while the others cannot. This is a common interview pattern combining prefix trees with grid traversal.
