Word Search II

visit.remove((r, c))

Remove the current cell from visited to backtrack.

This state restoration is the single most critical line in the backtracking algorithm; it ensures that the visited set correctly reflects the current path, allowing other DFS branches to explore the cell without false blockage.

curr.is_word = True

Mark the final trie node as a complete word.

After all characters are inserted, this flag marks the path as a complete word that can be reported during DFS.

def dfs(r, c, node, word):

Define the DFS function to explore board paths matching Trie prefixes.

DFS recursively explores neighbors, pruning paths that do not match any prefix in the Trie.

if (r < 0 or c < 0 or

Check if current position is out of bounds or invalid for exploration.

Boundary and pruning checks prevent invalid or redundant exploration, ensuring correctness and efficiency.

(r, c) in visit or board[r][c] not in node.children):

Check if column index exceeds board boundaries or cell is visited or character not in Trie children.

Ensures only valid, unvisited cells with matching Trie prefixes are explored, enabling pruning.

node = node.children[board[r][c]]

Advance the Trie node to the child corresponding to the current board character.

Moving down the Trie aligns the search path with the current prefix, enabling prefix validation.

if node.is_word:

Check if the current Trie node marks a complete word.

Detecting complete words during DFS allows adding valid words to the result set immediately.

self.children = {}

Initialize the children dictionary.

The children dictionary stores outgoing character transitions for prefix traversal.

self.is_word = False

Initialize the word-ending flag.

The is_word flag distinguishes a complete stored word from a prefix that merely continues to other nodes.

if c not in curr.children:

Check whether the character child is missing.

A missing child means the trie does not yet contain this prefix path and must create it.

curr.children[c] = TrieNode()

Create the missing trie child.

Creating a new TrieNode extends the trie to represent the new prefix.

root.add_word(w)

Insert the current word into the Trie.

Populating the Trie with all words enables prefix-based pruning during DFS.

res, visit = set(), set()

Initialize the result set and visited set.

The result set collects unique found words; the visited set tracks cells used in the current DFS path to prevent reuse.

return

Return early if any invalid condition is met.

Early return avoids unnecessary recursion and exploration of invalid paths.

visit.add((r, c))

Mark the current cell as visited.

Tracking visited cells prevents revisiting the same cell in the current path, maintaining path validity.

res.add(word)

Add the current word to the result set.

Storing found words ensures unique results and prevents duplicates.

dfs(r, c, root, "")

Invoke DFS from the current cell with the root Trie node and empty word.

This initiates the prefix-based search from each cell, enabling discovery of all valid words.

curr = curr.children[c]

Move to the child node for the current character.

Advancing the pointer moves insertion deeper along the word path.

root = TrieNode()

Create the root TrieNode for all words.

The root node serves as the entry point for all prefix searches and insertions.

r == ROWS or c == COLS or

Check if row index exceeds board boundaries.

Prevents index errors and invalid moves beyond the board.

word += board[r][c]

Append the current character to the forming word.

Building the current word string allows adding complete words to the result when found.

dfs(r + 1, c, node, word)

Recursively explore the cell below.

DFS explores all four directions to find all valid word paths.

dfs(r - 1, c, node, word)

Recursively explore the cell above.

DFS explores all four directions to find all valid word paths.

dfs(r, c + 1, node, word)

Recursively explore the cell to the right.

DFS explores all four directions to find all valid word paths.

dfs(r, c - 1, node, word)

Recursively explore the cell to the left.

DFS explores all four directions to find all valid word paths.

def __init__(self):

Define the TrieNode initializer.

The initializer defines the per-node state that every trie insertion and lookup depends on.

def add_word(self, word):

Define the trie word-insertion helper.

The add_word helper encapsulates insertion logic so each input word can be loaded into the trie consistently.

curr = self

Initialize the insertion pointer.

Insertion starts at the current trie root and walks one character at a time.

for c in word:

Iterate through the characters of the word.

Each character extends or follows one edge in the trie path for the word.

def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:

Define the findWords method.

This method is the entry point that builds the trie, searches the board, and returns all discovered words.

for w in words:

Iterate over each word in the input list.

Each word must be inserted into the Trie to build the prefix tree for efficient search.

for r in range(ROWS):

Iterate over each row in the board to start DFS.

Starting DFS from every cell ensures all possible word paths are explored.

for c in range(COLS):

Iterate over each column in the board to start DFS.

Starting DFS from every cell ensures all possible word paths are explored.

ROWS, COLS = len(board), len(board[0])

Store the number of rows and columns of the board.

Caching dimensions simplifies boundary checks during DFS.

return list(res)

Return the list of found words.

Converting the result set to a list provides the final output in the expected format.