Word Search II

1. Step 1: Initialize Solution.findWords

   Replace the empty starter with the first real state owned by Solution.findWords. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Assemble the primary transition

   Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.

3. Step 3: Pass the Two Found case

   Complete the readable core algorithm for one representative Interview case. The trie prunes every prefix that no requested word uses; the next checkpoint adds path-local visited state.

4. Step 4: Harden the Cannot Reuse Cell boundary

   Repair the reviewed boundary and pass the complete submission contract. DFS explores exactly every non-reusing board path whose prefix belongs to some dictionary word. A terminal identifies a complete word, and removing it emits that word once while trie pruning excludes no possible match.

• Temporarily mark a board cell and restore it after recursion so one path cannot reuse the same cell.
• trees and graphs
• recursion and backtracking

• LeetCode 212 — Word Search II

• Complete One Backtracking Frame(opens in a new tab)

  Complete One Backtracking Frame isolates before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element. That focused state discipline is required when implementing word search two as a complete Interview Problem.

• Follow Trie Edges(opens in a new tab)

  Follow Trie Edges isolates after matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match. That focused state discipline is required when implementing word search two as a complete Interview Problem.

• Visit Each Grid Component(opens in a new tab)

  Visit Each Grid Component isolates a cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. That focused state discipline is required when implementing word search two as a complete Interview Problem.

Insert words into a trie with a terminal word value. DFS from every cell, following trie children, marking the cell during recursion, and pop a found terminal to deduplicate it.

Why it works: DFS explores exactly every non-reusing board path whose prefix belongs to some dictionary word. A terminal identifies a complete word, and removing it emits that word once while trie pruning excludes no possible match.

class Solution:
    def findWords(self, board, words):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        trie = {}
        for word in words:
            node = trie
            for character in word:
                node = node.setdefault(character, {})
            node['$'] = word
        rows, columns = len(board), len(board[0])
        found = []
        def visit(row, column, node):
            if not (0 <= row < rows and 0 <= column < columns):
                return
            character = board[row][column]
            if character == '#' or character not in node:
                return
            child = node[character]
            word = child.pop('$', None)
            if word is not None:
                found.append(word)
            board[row][column] = '#'
            visit(row + 1, column, child)
            visit(row - 1, column, child)
            visit(row, column + 1, child)
            visit(row, column - 1, child)
            board[row][column] = character
        for row in range(rows):
            for column in range(columns):
                visit(row, column, trie)
        return found

• Word Search in a Character Grid(opens in a new tab)