Word Search II
HardPrompt
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 neighboring. The same letter cell may not be used more than once in a word.
Example 1:
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"]Example 2:
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j]is a lowercase English letter.1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i]consists of lowercase English letters.- All the strings of
wordsare unique.
Approaches
2 approaches with complexity analysis and trade-offs.
For each word in the words list, try to find it in the board by performing DFS search starting from each cell.
Algorithm
- For each word in the input array:
- For each cell in the board:
- If the current cell matches the first character of the word:
- Perform DFS to find the complete word
- Mark cells as visited during DFS
- Unmark cells when backtracking
- If the current cell matches the first character of the word:
- For each cell in the board:
- Add found words to the result set
- Return the list of found words
Walkthrough
This approach involves checking each word from the words list by attempting to find it on the board. For each word, we iterate through every cell on the board and try to match the word starting from that cell using DFS (Depth First Search).
class Solution { private int m, n; private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public List<String> findWords(char[][] board, String[] words) { Set<String> result = new HashSet<>(); m = board.length; n = board[0].length; for (String word : words) { boolean found = false; for (int i = 0; i < m && !found; i++) { for (int j = 0; j < n && !found; j++) { if (board[i][j] == word.charAt(0)) { boolean[][] visited = new boolean[m][n]; if (dfs(board, word, 0, i, j, visited)) { result.add(word); found = true; } } } } } return new ArrayList<>(result); } private boolean dfs(char[][] board, String word, int index, int i, int j, boolean[][] visited) { if (index == word.length()) return true; if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(index)) return false; visited[i][j] = true; for (int[] dir : directions) { int newI = i + dir[0]; int newJ = j + dir[1]; if (dfs(board, word, index + 1, newI, newJ, visited)) return true; } visited[i][j] = false; return false; }}Complexity
Time
O(N * M * 4^L) where N is the number of cells in the board, M is the number of words, and L is the maximum length of a word
Space
O(N) where N is the size of the board for the visited array in DFS
Trade-offs
Pros
Simple to implement and understand
Works well for small boards and word lists
Low space complexity
Cons
Very inefficient for large word lists
Repeats work for words with common prefixes
Time complexity grows exponentially with word length
Build a Trie data structure with all the words, then perform DFS on the board to find all possible words in the Trie.
Algorithm
- Build a Trie from all words in the input array
- For each cell in the board:
- Start DFS traversal
- Check if current path exists in Trie
- If a word is found, add to result
- Mark cells during traversal
- Backtrack and restore cells
- Return found words
Walkthrough
This approach first builds a Trie (prefix tree) containing all the words. Then, we perform a single DFS traversal of the board, checking if the current path exists in the Trie. This allows us to efficiently check multiple words simultaneously.
class Solution { class TrieNode { TrieNode[] children = new TrieNode[26]; String word = null; } private TrieNode buildTrie(String[] words) { TrieNode root = new TrieNode(); for (String word : words) { TrieNode node = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { node.children[index] = new TrieNode(); } node = node.children[index]; } node.word = word; } return root; } public List<String> findWords(char[][] board, String[] words) { List<String> result = new ArrayList<>(); TrieNode root = buildTrie(words); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { dfs(board, i, j, root, result); } } return result; } private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) { if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '#' || node.children[board[i][j] - 'a'] == null) return; char c = board[i][j]; node = node.children[c - 'a']; if (node.word != null) { result.add(node.word); node.word = null; // prevent duplicates } board[i][j] = '#'; dfs(board, i + 1, j, node, result); dfs(board, i - 1, j, node, result); dfs(board, i, j + 1, node, result); dfs(board, i, j - 1, node, result); board[i][j] = c; }}Complexity
Time
O(N * 4^L) where N is the number of cells in the board and L is the maximum length of a word. Trie construction is O(M*K) where M is total number of characters in all words
Space
O(M) where M is the total number of characters in all words (for the Trie structure)
Trade-offs
Pros
More efficient than brute force for large word lists
Avoids repeated work for words with common prefixes
Can stop early if prefix is not in Trie
Handles multiple words simultaneously
Cons
Requires additional space for Trie structure
Initial setup time to build Trie
More complex implementation
Solutions
Solution
class Trie { Trie [] children = new Trie [ 26 ]; int ref = - 1 ; public void insert ( String w , int ref ) { Trie node = this ; for ( int i = 0 ; i < w . length (); ++ i ) { int j = w . charAt ( i ) - 'a' ; if ( node . children [ j ] == null ) { node . children [ j ] = new Trie (); } node = node . children [ j ]; } node . ref = ref ; } } class Solution { private char [][] board ; private String [] words ; private List < String > ans = new ArrayList <>(); public List < String > findWords ( char [][] board , String [] words ) { this . board = board ; this . words = words ; Trie tree = new Trie (); for ( int i = 0 ; i < words . length ; ++ i ) { tree . insert ( words [ i ], i ); } int m = board . length , n = board [ 0 ]. length ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { dfs ( tree , i , j ); } } return ans ; } private void dfs ( Trie node , int i , int j ) { int idx = board [ i ][ j ] - 'a' ; if ( node . children [ idx ] == null ) { return ; } node = node . children [ idx ]; if ( node . ref != - 1 ) { ans . add ( words [ node . ref ]); node . ref = - 1 ; } char c = board [ i ][ j ]; board [ i ][ j ] = '#' ; int [] dirs = {- 1 , 0 , 1 , 0 , - 1 }; for ( int k = 0 ; k < 4 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x >= 0 && x < board . length && y >= 0 && y < board [ 0 ]. length && board [ x ][ y ] != '#' ) { dfs ( node , x , y ); } } board [ i ][ j ] = c ; } }class Trie { public: vector < Trie *> children ; int ref ; Trie () : children ( 26 , nullptr ) , ref ( - 1 ) {} void insert ( const string & w , int ref ) { Trie * node = this ; for ( char c : w ) { c -= 'a' ; if ( ! node -> children [ c ]) { node -> children [ c ] = new Trie (); } node = node -> children [ c ]; } node -> ref = ref ; } }; class Solution { public: vector < string > findWords ( vector < vector < char >>& board , vector < string >& words ) { Trie * tree = new Trie (); for ( int i = 0 ; i < words . size (); ++ i ) { tree -> insert ( words [ i ], i ); } vector < string > ans ; int m = board . size (), n = board [ 0 ]. size (); function < void ( Trie * , int , int ) > dfs = [ & ]( Trie * node , int i , int j ) { int idx = board [ i ][ j ] - 'a' ; if ( ! node -> children [ idx ]) { return ; } node = node -> children [ idx ]; if ( node -> ref != - 1 ) { ans . emplace_back ( words [ node -> ref ]); node -> ref = - 1 ; } int dirs [ 5 ] = { - 1 , 0 , 1 , 0 , - 1 }; char c = board [ i ][ j ]; board [ i ][ j ] = '#' ; for ( int k = 0 ; k < 4 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n && board [ x ][ y ] != '#' ) { dfs ( node , x , y ); } } board [ i ][ j ] = c ; }; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { dfs ( tree , i , j ); } } return ans ; } };class Trie : def __init__ ( self ): self . children = [ None ] * 26 self . w = '' # minor ajust, not a boolean is_end, but the whole word # so it's easier for dfs to save the word def insert ( self , w ): node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . w = w class Solution : def findWords ( self , board : List [ List [ str ]], words : List [ str ]) -> List [ str ]: def dfs ( node , i , j ): idx = ord ( board [ i ][ j ]) - ord ( 'a' ) if node . children [ idx ] is None : return node = node . children [ idx ] if node . w : ans . add ( node . w ) c = board [ i ][ j ] board [ i ][ j ] = '0' # 0 for visited already for a , b in [[ 0 , - 1 ], [ 0 , 1 ], [ 1 , 0 ], [ - 1 , 0 ]]: x , y = i + a , j + b if 0 <= x < m and 0 <= y < n and board [ x ][ y ] != '0' : dfs ( node , x , y ) board [ i ][ y ] = c trie = Trie () for w in words : trie . insert ( w ) ans = set () m , n = len ( board ), len ( board [ 0 ]) for i in range ( m ): for j in range ( n ): dfs ( trie , i , j ) return list ( ans ) ################ class Trie : def __init__ ( self ): self . children : List [ Trie | None ] = [ None ] * 26 self . ref : int = - 1 def insert ( self , w : str , ref : int ): node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . ref = ref class Solution : def findWords ( self , board : List [ List [ str ]], words : List [ str ]) -> List [ str ]: def dfs ( node : Trie , i : int , j : int ): idx = ord ( board [ i ][ j ]) - ord ( 'a' ) if node . children [ idx ] is None : return node = node . children [ idx ] if node . ref >= 0 : ans . append ( words [ node . ref ]) node . ref = - 1 c = board [ i ][ j ] board [ i ][ j ] = '#' for a , b in pairwise (( - 1 , 0 , 1 , 0 , - 1 )): x , y = i + a , j + b if 0 <= x < m and 0 <= y < n and board [ x ][ y ] != '#' : dfs ( node , x , y ) board [ i ][ j ] = c tree = Trie () for i , w in enumerate ( words ): tree . insert ( w , i ) m , n = len ( board ), len ( board [ 0 ]) ans = [] for i in range ( m ): for j in range ( n ): dfs ( tree , i , j ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.