LeetEye LeetEye
Medium Trie ~5 min

Word Search II

tries word-search-ii

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.

Examples

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: []
Key Insight

Build a trie from words. DFS on the grid, but use trie to prune impossible paths early.

Build trie from words. DFS on grid while walking trie simultaneously. Prune when path isn't a trie prefix. Store found words, remove from trie to avoid duplicates.

How to Approach This Problem

Pattern Recognition: When you see keywords like word search ii tries, think Trie.

Step-by-Step Reasoning

1 Using a trie for the word list helps because:
Answer: We can check if current path is a valid prefix in O(1)
Trie lets us know instantly if a path could lead to any word, enabling early pruning.
2 We should stop exploring a grid path when:
Answer: Current path is not a prefix of any word
If no word starts with this prefix, don't waste time continuing.
3 When DFS reaches a complete word in trie:
Answer: Add to results and continue exploring
"oath" might be found, but "oaths" could also exist. Continue exploring after finding a word.
4 To ensure the same cell isn't used twice in a word:
Answer: Mark it during DFS, unmark on backtrack
Temporarily mark during exploration, restore when backtracking. Standard DFS pattern.
5 After finding a word, we can:
Answer: Remove it from trie to avoid duplicates
Prevents finding the same word again. Also allows pruning empty trie branches.

Solution

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

def findWords(board: List[List[str]], words: List[str]) -> List[str]:
    # Build trie
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word = word
    
    result = []
    rows, cols = len(board), len(board[0])
    
    def dfs(r, c, node):
        char = board[r][c]
        if char not in node.children:
            return
        
        next_node = node.children[char]
        
        # Found a word
        if next_node.word:
            result.append(next_node.word)
            next_node.word = None  # Avoid duplicates
        
        # Mark visited
        board[r][c] = '#'
        
        # Explore neighbors
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != &#039;#':
                dfs(nr, nc, next_node)
        
        # Restore
        board[r][c] = char
    
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    
    return result

Complexity Analysis

Time O(m * n * 4^L)
Space O(total chars in words)

Master This Pattern

Build intuition with interactive MCQs. Practice Trie problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye