LeetCode Solutions Blog

Word Search II

Number: 212

Difficulty: Hard

Paid? No

Problem Description

Given an m x n board of characters and a list of unique words, return all words from the list that can be formed by letters on the board. Each word must be constructed from letters of sequentially adjacent cells (horizontally or vertically), and the same cell may not be used more than once in a word.

Key Insights

Use Depth-First Search (DFS) to explore possible words starting from each board cell.
Build a Trie (prefix tree) to store the words for O(1) prefix checks and efficient pruning.
Mark visited cells and restore them after DFS to avoid revisiting in the current search path.
Prune search paths early if the current prefix is not part of any word in the Trie.

Space and Time Complexity

Time Complexity: O(m * n * 4^L) in the worst case, where L is the maximum word length; however, using a Trie prunes unnecessary paths. Space Complexity: O(K) for the Trie storage, where K is the total number of letters in all words, plus O(m * n) auxiliary space for recursion and board marking.

Solution

We first insert all words into a Trie data structure to allow quick lookups of prefixes. Then, for each cell in the board, we perform DFS. During DFS, if the current path matches a Trie node that represents a complete word, we add that word to the result list and mark it as found to avoid duplicates. We continue exploring adjacent cells (up, down, left, right) while marking the cell as visited. After exploring, we restore the original letter for further DFS calls. This combination of Trie and DFS with backtracking efficiently finds valid words on the board.

Code Solutions

# Define a TrieNode for building the Trie.
class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # Stores complete word at the end node

class Solution:
    def findWords(self, board, words):
        # Build the Trie from the list of words.
        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  # Mark the end of a word
        
        result = []
        m, n = len(board), len(board[0])
        
        # Define the DFS helper function.
        def dfs(i, j, node):
            char = board[i][j]
            if char not in node.children:
                return
            next_node = node.children[char]
            if next_node.word:
                result.append(next_node.word)
                next_node.word = None  # Avoid duplicate entries
            
            board[i][j] = '#'  # Mark the current cell as visited
            # Explore all four adjacent directions.
            for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                ni, nj = i + dx, j + dy
                if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':
                    dfs(ni, nj, next_node)
            board[i][j] = char  # Restore the original character
        
        # Start DFS from each cell.
        for i in range(m):
            for j in range(n):
                dfs(i, j, root)
        return result