Word Search II

https://leetcode.com/problems/word-search-ii/

• Search the word in 2D grid, classic backtracking problem.
• Utilizes the trie data structure. Implemented with dictionary.

# trie initialization
trie = {}
for word in words:
    node = trie
    for char in word:
        node = node.setdefault(char, {})
    node['$'] = word # genius!
 
# constants initialization
row_num = len(board)
col_num = len(board[0])
matched = []
 
# backtracking helper
def backtrack(row, col, parent) -> None:
    char = board[row][col]
    node = parent[char]
    # if word is matched
    if word := node.pop('$', False):
        matched.append(word)
 
    board[row][col] = '#'  # mark as visited
    offsets = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    for row_offset, col_offset in offsets:
        new_row = row + row_offset
        new_col = col + col_offset
        # check indices
        if not (
            0 <= new_row < row_num and
            0 <= new_col < col_num and
            board[new_row][new_col] in node
        ):
            continue
        backtrack(new_row, new_col, node)
    board[row][col] = char  # restore cell
    # optimization
    if not node:
        parent.pop(char)
 
for row in range(row_num):
    for col in range(col_num):
        if board[row][col] in trie:
            backtrack(row, col, trie)
 
return matched