LeetCode 212: Word Search II Solution in Python Explained

Problem Statement

In LeetCode 212: Word Search II, you’re given:

• board: A 2D array of characters (m × n).
• words: A list of strings to find on the board.
• Your task is to return a list of all words from words that can be formed by connecting adjacent cells (up, down, left, right) without reusing cells.

This builds on LeetCode 211: Design Add and Search Words Data Structure by applying Trie to a grid, differing from scheduling in LeetCode 210: Course Schedule II.

Constraints

• m == board.length.
• n == board[i].length.
• 1 ≤ m, n ≤ 12.
• board[i][j] is a lowercase English letter.
• 1 ≤ words.length ≤ 3 * 10⁴.
• 1 ≤ words[i].length ≤ 10.
• words[i] contains only lowercase letters.
• All words are unique.

Examples

Let’s see some cases:

Copy codeInput: 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"]
Explanation: "eat" (down from (1,0)) and "oath" (diagonal from (0,0)) are found.

Copy codeInput: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Explanation: "abcb" requires reusing cells, not possible.

These examples show we’re finding valid word paths.

Understanding the Problem

How do we solve LeetCode 212: Word Search II in Python? For the board [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]] and words = ["oath","pea","eat","rain"], we need to find "oath" (o-a-t-h) and "eat" (e-a-t). A naive DFS for each word from each cell is O(mn4^LW) (L = max word length, W = number of words), which is slow. We’ll use a Trie to optimize: 1. Trie with DFS: O(mn4^L) time, O(sum of letters in words) space—our best solution. 2. DFS with Set: O(mn4^LW) time, O(W) space—an alternative.

Let’s dive into the best solution.

Best Solution: Trie with DFS Approach

Explanation

The Trie with DFS approach combines a Trie and backtracking:

• Build a Trie from words, each node storing characters and a word marker.
• For each cell, DFS explores all paths, using the Trie to prune invalid branches.
• Mark visited cells (e.g., with #) to avoid reuse, collect found words.

This runs in O(mn4^L) time (explore each cell with bounded DFS) and O(sum of letters in words) space (Trie size), making it efficient—our best solution.

For ["oath","eat"], it finds both words faster than checking each individually.

Step-by-Step Example

Example 1: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","eat"]

Goal: Return ["eat","oath"].

• Step 1: Build Trie.
• {'o': {'a': {'t': {'h': {'#': 'oath'{{{{, 'e': {'a': {'t': {'#': 'eat'{{{{.
• Step 2: DFS from each cell.
• (0,0) = 'o':
• Match o, explore:
• (1,0) = 'e': No match, backtrack.
• (0,1) = 'a': Match oa, explore:
• (1,1) = 't': Match oat, explore:
• (2,1) = 'h': Match oath, add "oath", backtrack.
• (1,0) = 'e':
• Match e, explore:
• (1,1) = 'a': Match ea, explore:
• (1,2) = 't': Match eat, add "eat", backtrack.
• Step 3: Finish.
• Result: ["eat","oath"] (order may vary).

Example 2: board = [["a"]], words = ["a"]

Goal: Return ["a"].

• Step 1: Trie: {'a': {'#': 'a'{{.
• Step 2: (0,0) = 'a', match a, add "a".
• Output: ["a"].

How the Code Works (Trie with DFS) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codeclass Trie:
    def __init__(self):
        self.root = {{
        self.end = '#'

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {{)
        node[self.end] = word  # Store full word

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    # Line 1: Build Trie
    trie = Trie()
    # Create Trie instance (e.g., Trie())
    for word in words:
        # Iterate words (e.g., "oath")
        trie.insert(word)
        # Add to Trie (e.g., 'o' → 'a' → 't' → 'h')

    # Line 2: Initialize variables
    m, n = len(board), len(board[0])
    # Board dimensions (e.g., 4, 4)
    result = set()
    # Unique found words (e.g., set())

    # Line 3: DFS helper function
    def dfs(i: int, j: int, node):
        # Explore board from (i,j) with Trie node
        if trie.end in node:
            # Word found (e.g., 'oath')
            result.add(node[trie.end])
            # Add to result (e.g., "oath")

        temp = board[i][j]
        # Save current char (e.g., 'o')
        board[i][j] = '#'
        # Mark visited (e.g., '#')

        for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            # Four directions (up, down, left, right)
            ni, nj = i + di, j + dj
            # New coordinates (e.g., (1,0))
            if (0 <= ni < m and 0 <= nj < n and 
                board[ni][nj] != '#' and board[ni][nj] in node):
                # Valid move and char in Trie (e.g., 'a')
                dfs(ni, nj, node[board[ni][nj]])
                # Recurse (e.g., dfs(0,1, {'a': ...{))

        board[i][j] = temp
        # Restore char (e.g., 'o')

    # Line 4: Start DFS from each cell
    for i in range(m):
        # Rows (e.g., 0 to 3)
        for j in range(n):
            # Columns (e.g., 0 to 3)
            if board[i][j] in trie.root:
                # Char in Trie root (e.g., 'o')
                dfs(i, j, trie.root)
                # Explore (e.g., dfs(0,0, {'o': ...{))

    # Line 5: Return result
    return list(result)
    # Convert set to list (e.g., ["eat","oath"])

This solution optimizes search with a Trie.

Alternative: DFS with Set Approach

Explanation

The DFS with Set approach checks each word individually:

• Store words in a set.
• For each cell, DFS explores all possible paths up to max word length.
• If a path matches a word, add it to the result.

It’s O(mn4^L*W) time (W = number of words) and O(W) space, simpler but less efficient.

Step-by-Step Example

For board = [["o","a"],["e","t"]], words = ["oat","eat"]:

• (0,0) = 'o': Explore o-a, no oat, backtrack.
• (1,0) = 'e': e-a-t, add "eat".
• (0,0) with longer path: Eventually finds "oat".
• Output: ["eat","oat"].

How the Code Works (DFS with Set)

Copy codedef findWordsDFS(board: list[list[str]], words: list[str]) -> list[str]:
    m, n = len(board), len(board[0])
    words_set = set(words)
    result = set()
    max_len = max(len(w) for w in words)

    def dfs(i, j, curr_word):
        if curr_word in words_set:
            result.add(curr_word)

        if len(curr_word) >= max_len:
            return

        temp = board[i][j]
        board[i][j] = '#'
        for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':
                dfs(ni, nj, curr_word + board[ni][nj])
        board[i][j] = temp

    for i in range(m):
        for j in range(n):
            dfs(i, j, board[i][j])

    return list(result)

Complexity

• Trie with DFS:
• Time: O(m*n*4^L) – Trie prunes branches.
• Space: O(sum of letters in words) – Trie size.
• DFS with Set:
• Time: O(m*n*4^L*W) – check each word.
• Space: O(W) – set of words.

Efficiency Notes

Trie with DFS is our best solution for its efficiency with many words, leveraging Trie pruning. DFS with Set is simpler but scales poorly with word count.

Key Insights

• Trie: Prefix optimization.
• DFS: Path exploration.
• Backtracking: Avoids cell reuse.

Additional Example

For board = [["a","b"]], words = ["ab","ba"]:

• Trie: Finds "ab", not "ba".
• Output: ["ab"].

Edge Cases

• Single cell: ["a"], works.
• No words: [].
• Large board: Both scale, Trie faster.

Final Thoughts

LeetCode 212: Word Search II in Python is a thrilling blend of Trie and DFS. Trie with DFS excels in performance, while DFS with Set offers simplicity. Want more? Try LeetCode 79: Word Search or LeetCode 208: Implement Trie (Prefix Tree). Test your skills—Solve LeetCode 212 on LeetCode with the first example (expecting ["eat","oath"])—find those words today!