DSA problem
Word Search II
Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once in a single word.
A naive solution runs the classic Word Search I algorithm once per word, calling DFS from every cell for each query word. That costs O(W * m * n * 4^L) where W is the number of words and L is the maximum word length — far too slow when W is in the thousands. The redundancy is obvious: every DFS re-explores the same paths in the grid from scratch.
The optimal approach inverts the problem. Build a Trie from the entire word list, then walk the grid only once, descending in the Trie in lockstep with the DFS. At every cell, we ask the Trie a single O(1) question — "does any word use this letter next?" — and prune entire branches when the answer is no. The Trie effectively encodes all W words into one shared prefix tree.
Two extra optimisations make this fast in practice. First, when we visit a Trie node whose word field is set, we add that word to the result and clear the field so we never report it twice. Second, when a Trie leaf is exhausted, we can splice it out of its parent — over time this collapses the Trie and accelerates later DFS calls. The total complexity becomes O(m * n * 4^L) regardless of how many words are in the list.
Examples
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]["eat","oath"]board = [["a","b"],["c","d"]], words = ["abcb"][]board = [["a"]], words = ["a"]["a"]Constraints
- m == board.length
- n == board[i].length
- 1 <= m, n <= 12
- 1 <= words.length <= 3 * 10^4
- 1 <= words[i].length <= 10
- All strings of words are unique.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.