Word Search II
The key idea
Searching every word independently rescans the board once per word. Instead, build a trie of all the words and run ONE DFS from each cell: the trie tells you in O(1) whether the prefix you have spelled so far can still lead to any word, so a dead branch is pruned the instant it leaves the trie.
Problem
Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must be built from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a single word.
Constraints
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j]is a lowercase English letter1 <= words.length <= 3 * 10^41 <= words[i].length <= 10words[i]consists of lowercase English letters- All the strings of
wordsare unique
Examples
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Complexity
Time: O(m*n*4*3^(L-1)) Space: O(sum(L))
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization