word_search.py

class Solution:
    def exist(self, board, word):
        if not board:
            return False

        rows, cols = len(board), len(board[0])

        def backtrack(i, j, idx):
            if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != word[idx]:
                return False

            if idx == len(word) - 1:
                return True

            temp = board[i][j]
            board[i][j] = "#"
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

            for i_offset, j_offset in directions:
                r, c = i + i_offset, j + j_offset
                if backtrack(r, c, idx + 1):
                    return True

            board[i][j] = temp
            return False

        for i in range(rows):
            for j in range(cols):
                if board[i][j] == word[0] and backtrack(i, j, 0):
                    return True

        return False

        # Time Complexity: O(rows * cols * 4^L)
        # Space Complexity: O(L)


if __name__ == "__main__":

    solution = Solution()

    board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
    word = "ABCCED"
    result = solution.exist(board, word)
    assert result == True
    print(result)
    print("Test Case 1 Passed!")