deepSWE.io

Word Search II

TriesMatrixDFS

Problem Statement

Given an m x n board of characters and a list of strings words, return all words on the board that can be formed by traversing adjacent cells (horizontally or vertically). Each letter on the board can only be used once in each word.

Example Board

Words to find: ["oath", "pea", "eat", "rain"]

Output: ["eat", "oath"]

Explanation:

"eat" exists on the board
"oath" exists on the board
"pea" and "rain" are not on the board

Trie Structure

Found Word Path

Complete Word

Approach:

Build a trie from the word list
Use DFS to explore board paths
Check if current path exists in trie
Mark visited cells to avoid reuse

Key Concepts

• Use trie to efficiently store and search word prefixes
• DFS with backtracking to explore all possible paths
• Track visited cells to prevent reuse
• Time complexity: O(M × N × 4^L) where L is max word length
• Space complexity: O(total characters in all words)

Algorithm Explanation

This solution combines a Trie for efficient word lookup with DFS for board traversal. The Trie helps us quickly validate if our current path could form a valid word.

Key Operations

Build Trie: Create a trie from the word list for efficient prefix checking.
Board DFS: For each cell, explore all possible paths using depth-first search.
Word Validation: Use trie to check if current path forms a valid word.
Track Visited: Mark cells as visited during DFS to avoid reusing them.

Optimization Tips

Stop DFS when current path is not a valid prefix in trie
Remove words from trie after finding them to avoid duplicates
Use board cell itself as visited marker to save space
Track found words in a set for O(1) lookup

Word Search Visualization

Finding words in the grid using Trie + DFS

Board

Found Words

oath

pea

eat

rain

Start: Initialize search

Starting the word search...

Step 1 of 54

Code Example

class TrieNode:
    def __init__(self):
        self.children = {}  # character -> TrieNode
        self.is_word = False
        self.word = None  # Store complete word at end nodes
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
        node.word = word

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        """
        Find all words from the word list that exist in the board.
        Time: O(M * N * 4^L) where M×N is board size, L is max word length
        Space: O(total chars in all words) for the trie
        """
        # Build trie
        trie = Trie()
        for word in words:
            trie.insert(word)
            
        found_words = set()
        m, n = len(board), len(board[0])
        
        def dfs(i: int, j: int, node: TrieNode) -> None:
            # Check boundaries and if letter matches
            if (i < 0 or i >= m or j < 0 or j >= n or 
                board[i][j] not in node.children):
                return
            
            char = board[i][j]
            next_node = node.children[char]
            
            # Found a word
            if next_node.is_word:
                found_words.add(next_node.word)
            
            # Mark cell as visited
            board[i][j] = '#'
            
            # Explore all four directions
            for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                dfs(i + di, j + dj, next_node)
            
            # Restore the cell
            board[i][j] = char
        
        # Try each cell as starting point
        for i in range(m):
            for j in range(n):
                dfs(i, j, trie.root)
                
        return list(found_words)