Word Search II – Solution & Complexity

def find_words(board: list[str], words: list[str]) -> list[str]:
    trie = {}
    end = "#"
    for word in words:
        node = trie
        for char in word:
            node = node.setdefault(char, {})
        node[end] = word

    rows = len(board)
    cols = len(board[0])
    grid = [list(row) for row in board]
    found = []

    def dfs(r: int, c: int, node: dict) -> None:
        if not (0 <= r < rows and 0 <= c < cols):
            return
        char = grid[r][c]
        if char == "#" or char not in node:
            return

        nxt = node[char]
        word = nxt.pop(end, None)
        if word is not None:
            found.append(word)

        grid[r][c] = "#"
        dfs(r + 1, c, nxt)
        dfs(r - 1, c, nxt)
        dfs(r, c + 1, nxt)
        dfs(r, c - 1, nxt)
        grid[r][c] = char

    for row in range(rows):
        for col in range(cols):
            dfs(row, col, trie)

    return sorted(found)