Skip to main content

🟥 Word Search II (#212)

🔗 Problem Link​

📋 Problem Statement​

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 Insights & Approach​

Core Observation: Build Trie from words, then DFS from each cell to find words. More efficient than searching each word separately.

Why Trie + DFS?

  • Build trie: O(W * L) where W = words, L = avg length
  • Search: O(M * N * 4^L)
  • Better than Word Search I repeated W times

Approaches:

  1. Trie + DFS with backtracking: Optimal

Pattern: "Trie + 2D Grid DFS" for multi-word search.

🐍 Solution: Python​

Approach: Trie + DFS Backtracking​

Time Complexity: O(M * N * 4^L) | Space Complexity: O(W * L)

from typing import List

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

class Solution:
    def findWords(self, 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

        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r, c, node):
            char = board[r][c]

            if char not in node.children:
                return

            node = node.children[char]

            # Found word
            if node.word:
                result.append(node.word)
                node.word = None  # Avoid duplicates

            # Mark visited
            board[r][c] = '#'

            # Explore 4 directions
            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] != '#':
                    dfs(nr, nc, node)

            # Backtrack
            board[r][c] = char

        # Try from each cell
        for r in range(rows):
            for c in range(cols):
                if board[r][c] in root.children:
                    dfs(r, c, root)

        return result

🔵 Solution: Golang​

Approach: Trie + DFS​

Time Complexity: O(M * N * 4^L) | Space Complexity: O(W * L)

type TrieNode struct {
    children map[byte]*TrieNode
    word     string
}

func findWords(board [][]byte, words []string) []string {
    // Build trie
    root := &TrieNode{children: make(map[byte]*TrieNode)}
    for _, word := range words {
        node := root
        for i := 0; i < len(word); i++ {
            char := word[i]
            if _, exists := node.children[char]; !exists {
                node.children[char] = &TrieNode{children: make(map[byte]*TrieNode)}
            }
            node = node.children[char]
        }
        node.word = word
    }

    rows, cols := len(board), len(board[0])
    result := []string{}

    var dfs func(r, c int, node *TrieNode)
    dfs = func(r, c int, node *TrieNode) {
        char := board[r][c]

        if _, exists := node.children[char]; !exists {
            return
        }

        node = node.children[char]

        if node.word != "" {
            result = append(result, node.word)
            node.word = "" // Avoid duplicates
        }

        // Mark visited
        board[r][c] = '#'

        // Explore 4 directions
        dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
        for _, dir := range dirs {
            nr, nc := r+dir[0], c+dir[1]
            if nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] != '#' {
                dfs(nr, nc, node)
            }
        }

        // Backtrack
        board[r][c] = char
    }

    // Try from each cell
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if _, exists := root.children[board[r][c]]; exists {
                dfs(r, c, root)
            }
        }
    }

    return result
}

📚 References​