LeetCode #79: Word Search

LeetCode Solutions

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

In the Word Search problem, we are given a 2D grid of characters and a word to search for. We need to check if the given word exists in the grid, where the word can be constructed from letters of sequentially adjacent cells (horizontally or vertically adjacent cells).

To solve this problem, we can use the Depth-First Search (DFS) algorithm. We start by iterating over each cell in the grid and check if the first character of the given word matches the current cell. If it matches, we start the DFS algorithm from that cell to find the remaining characters of the word. During the DFS algorithm, we check if the current cell has already been visited or if the current character of the word does not match the character in the current cell. If any of these conditions are true, we backtrack to the previous cell and continue with the next cell in the grid. If we find all the characters of the word by visiting adjacent cells, we return True, else we return False.

Here are the steps to solve the Word Search problem using DFS:

  1. Iterate over each cell in the grid.
  2. For each cell, check if the first character of the word matches the current cell.
  3. If the first character matches, start the DFS algorithm from that cell to find the remaining characters of the word.
  4. During the DFS algorithm, check if the current cell has already been visited or if the current character of the word does not match the character in the current cell.
  5. If any of the above conditions are true, backtrack to the previous cell and continue with the next cell in the grid.
  6. If we find all the characters of the word by visiting adjacent cells, return True.
  7. If we have checked all cells in the grid and not found the word, return False.

Here’s the solution using DFS algorithm in Python:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        def dfs(i, j, k):
            if k == len(word):
                return True
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
                return False
            temp, board[i][j] = board[i][j], "/"
            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)
            board[i][j] = temp
            return res
            
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False

Time and Space Complexity

The time complexity of the solution is O(N * 3^L), where N is the number of cells in the board and L is the length of the word to be searched. For each cell, we can explore up to three directions, except for the previous cell where we came from. In the worst case, we need to explore all the cells on the board, which is N, and for each cell, we have a branching factor of 3. Therefore, the time complexity of the solution is O(N * 3^L).

The space complexity of the solution is O(L), where L is the length of the word to be searched. This is because we use a recursion stack to keep track of the current position in the board and the current index of the character in the word. The maximum depth of the recursion stack is the length of the word, which is L. Therefore, the space complexity of the solution is O(L).