# Word Search II
**Difficulty:** HARD
[External](https://leetcode.com/problems/word-search-ii)
Canonical: https://scaleengineer.com/dsa/problems/word-search-ii
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array, String, Trie, Matrix
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Cisco](https://scaleengineer.com/companies/cisco), [DoorDash](https://scaleengineer.com/companies/doordash), [Google](https://scaleengineer.com/companies/google), [Karat](https://scaleengineer.com/companies/karat), [PayPal](https://scaleengineer.com/companies/paypal), [Roblox](https://scaleengineer.com/companies/roblox), [Snowflake](https://scaleengineer.com/companies/snowflake), [Wix](https://scaleengineer.com/companies/wix), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [Capital One](https://scaleengineer.com/companies/capital-one), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [Instacart](https://scaleengineer.com/companies/instacart), [Block](https://scaleengineer.com/companies/block), [Aurora](https://scaleengineer.com/companies/aurora)
---
## 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 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:**

![](https://assets.glich.co/dsa/word-search-ii/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/word-search-ii/image1.jpg) 

**Input:** board = [["a","b"],["c","d"]], words = ["abcb"]
**Output:** []

**Constraints:**

* `m == board.length`
* `n == board[i].length`
* `1 <= m, n <= 12`
* `board[i][j]` is a lowercase English letter.
* `1 <= words.length <= 3 * 104`
* `1 <= words[i].length <= 10`
* `words[i]` consists of lowercase English letters.
* All the strings of `words` are unique.

# Approaches
## Brute Force DFS
For each word in the words list, try to find it in the board by performing DFS search starting from each cell.
**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
**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
### Explanation
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).

```java
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;
    }
}
```
### Algorithm
1. 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
2. Add found words to the result set
3. Return the list of found words

## Trie-based DFS Solution
Build a Trie data structure with all the words, then perform DFS on the board to find all possible words in the Trie.
**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)
**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
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Build a Trie from all words in the input array
2. 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
3. Return found words

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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 ans
```