Word Search II - Solution & Explanation

Problem Overview: You get an m x n board of characters and a list of words. A word can be formed by moving horizontally or vertically across adjacent cells without reusing the same cell in one path. The task is to return every word from the list that exists in the grid.

Approach 1: Backtracking and HashSet (O(W * m * n * 4^L) time, O(L) space)

This approach treats each word independently. For every word in the dictionary, start a DFS from every board cell that matches the first character. Use backtracking to explore four directions (up, down, left, right) while marking cells as visited so they are not reused in the same path. If the DFS successfully matches all characters of the word, add it to a result HashSet to avoid duplicates. The main drawback is repeated work: many prefixes overlap between words, yet the search restarts from scratch for each one. The worst‑case time complexity becomes O(W * m * n * 4^L), where W is the number of words and L is the maximum word length. Space complexity is O(L) for the recursion stack.

This method is straightforward and easy to implement, but it becomes slow when the word list is large because the board is scanned repeatedly for similar prefixes.

Approach 2: Backtracking with Trie (O(m * n * 4^L) time, O(N) space)

The optimized approach builds a Trie from the list of words before exploring the grid. A Trie stores shared prefixes, so multiple words that begin with the same characters reuse the same search path. Start DFS from each cell in the board, but only continue exploring if the current prefix exists in the Trie. If a Trie node marks the end of a word, add that word to the result immediately.

This pruning drastically reduces unnecessary exploration. If the board path forms a prefix that doesn't exist in the Trie, the search stops early. Each DFS step checks a child node in the Trie, which is an O(1) lookup. The search still explores up to four directions per step, leading to worst‑case complexity O(m * n * 4^L), but in practice it is much faster due to prefix pruning. Space complexity is O(N) for the Trie, where N is the total number of characters across all words.

This technique combines backtracking with a Trie to efficiently share prefix searches. The board traversal itself is a typical matrix DFS problem.

Recommended for interviews: Interviewers expect the Trie + backtracking solution. The HashSet approach demonstrates understanding of DFS search on a grid, but it repeats work for overlapping prefixes. Using a Trie shows that you can optimize prefix searches and reduce redundant exploration, which is the key insight for this problem.