Word Search II – Solution & Complexity

• Running a separate Word Search DFS for each candidate word repeats the same board-prefix checks over and over.
• The natural shared structure is a trie: words with the same prefix should share the same search prefix too.

• The brute-force strategy is: for each word, run the usual backtracking search from every board cell.
• That can be acceptable for one word, but with thousands of words it multiplies the board search cost by the dictionary size.

• Insert every word into a trie. While traversing the board, stop immediately when the current path no longer matches any trie edge.
• Whenever a trie node marks a complete word, add it to the answer and clear that marker so duplicates are not reported twice.
• Sort the final answer lexicographically before returning so every language produces the same deterministic output.

The trie shares prefix work across all words, which is the key improvement over checking each word independently.

• Returning duplicates when the same word can be formed along multiple paths or appears multiple times in the dictionary.
• Forgetting to restore a board cell after recursion, which corrupts sibling DFS branches.
• Follow-up: after a word is found, you can prune empty trie branches upward so future searches stop even earlier.