Exploring Words: Solving the Grid Word Search Problem with DFS Algorithm
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires us to find whether a given word can be constructed from the charac
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to find whether a given word can be constructed from the characters of the given grid such that adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. The problem can be solved using the Depth First Search (DFS) algorithm. The DFS algorithm works by exploring as far as possible along each branch before backtracking. It is well-suited for problems that require searching through all possible paths.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can approach the problem using the DFS algorithm. We start by iterating through each cell in the grid. For each cell, we check whether the current cell matches the first character of the given word. If the current cell matches the first character of the word, we start a DFS search from that cell, looking for the rest of the characters in the word.\n\nFor each DFS search, we explore all four directions, i.e., up, down, left, and right, to find the next character in the word. We mark the current cell as visited to ensure that we do not use the same cell more than once. If we find the entire word, we return True, else we continue the search from the next unvisited cell.\n\nWe need to keep track of the visited cells to ensure that we do not use the same cell more than once. To mark a cell as visited, we can replace the character in the cell with a special character, such as \'/\'. After completing the DFS search, we can restore the original value of the cell.\n# Complexity\n- Time complexity: The time complexity of the DFS algorithm is proportional to the number of cells in the grid, i.e., O(mn), where m is the number of rows and n is the number of columns. In the worst case, we may have to explore all possible paths to find the word. For each cell, we explore at most four directions, so the time complexity of the DFS search is O(4^k), where k is the length of the word. Therefore, the overall time complexity of the algorithm is O(mn*4^k).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The space complexity of the algorithm is O(k), where k is the length of the word. This is the space required to store the recursive stack during the DFS search.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -> bool:\n        def dfs(i: int, j: int, k: int) -> bool:\n            if k == len(word):\n                return True\n            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:\n                return False\n            temp, board[i][j] = board[i][j], \'/\'\n            res = dfs(i+1, j, k+1) or dfs(i-1, j, k+1) or dfs(i, j+1, k+1) or dfs(i, j-1, k+1)\n            board[i][j] = temp\n            return res\n        \n        m, n = len(board), len(board[0])\n        for i in range(m):\n            for j in range(n):\n                if dfs(i, j, 0):\n                    return True\n        return False\n\n```\n\n# Code Explanation \n\nThis is a Python implementation of the depth-first search algorithm to find if a word exists in a given board of characters.\n\nThe `exist` method takes in two parameters, `board` and `word`, which are the 2D list of characters representing the board and the string representing the word to find, respectively. The method returns a boolean value, `True` if the word exists in the board, and `False` otherwise.\n\nThe algorithm uses a helper function `dfs` to search for the word starting from a given position in the board. The `dfs` function takes in three parameters, `i`, `j`, and `k`, which are the row and column indices of the current position in the board and the index of the current character in the word, respectively. The function returns a boolean value, `True` if the word can be formed starting from this position, and `False` otherwise.\n\nThe `dfs` function first checks if the end of the word has been reached, in which case it returns `True`. If the current position is out of the board or does not match the current character in the word, the function returns `False`.\n\nIf the current position matches the current character in the word, the function temporarily changes the character at the current position to `\'/\'` to mark it as visited and prevent revisiting it in the search. It then recursively calls itself with the adjacent positions (up, down, left, and right) and the next index in the word. If any of the recursive calls returns `True`, the function returns `True` as well.\n\nAfter the search from the current position is finished, the function restores the original character at the current position and returns the final result.\n\nThe `exist` function first gets the dimensions of the board using the `len` function. It then iterates through each cell in the board using nested loops. For each cell, it calls the `dfs` function starting from that position with the first character in the word. If `dfs` returns `True`, the function immediately returns `True` as well since the word has been found. If no word is found after iterating through all cells, the function returns `False`.
['Array', 'Backtracking', 'Depth-First Search', 'Matrix', 'Python3']