# [[word-search|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. ```python # 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 ```