48 / 75
Build Trie from words, then DFS on board checking Trie nodes to find all matching words.
Example:
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']Common Mistakes:
- Doing DFS for each word separately (too slow - O(words * m * n * 4^L))
- Not building Trie to search all words simultaneously
- Forgetting to mark cells as visited during DFS
- Not handling duplicate words in results
- Not restoring board state after DFS
Notes:
Much more efficient than Word Search I repeated. Time O(m*n*4^L) where L=max word length. Space O(total chars in words) for Trie.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Build Trie from words, then DFS on board checking Trie nodes to find all matching words.
Example:
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']Common Mistakes:
- Doing DFS for each word separately (too slow - O(words * m * n * 4^L))
- Not building Trie to search all words simultaneously
- Forgetting to mark cells as visited during DFS
- Not handling duplicate words in results
- Not restoring board state after DFS
Notes:
Much more efficient than Word Search I repeated. Time O(m*n*4^L) where L=max word length. Space O(total chars in words) for Trie.
48/75
Word Search II