Word Search

To solve this coding challenge, you need to implement a function that will check if a word exists within a given grid, where the word can be formed by sequentially adjacent cells. This involves a backtracking approach to explore every possible path by looking at each cell and its neighboring cells recursively.

Step-by-Step Explanation

1. Initialization and Validation :
• First, ensure the input grid (
  board
  ) and the target word (
  word
  ) are valid according to the constraints provided.
• We will initialize a backtracking helper function to search for the word starting from any cell in the grid.
2. Helper Function - Backtracking :
• The backtracking function checks whether the word can be formed starting from a given cell
  (i, j)
  and position
  k
  in the word.
• If
  k
  equals the length of the word, it means the entire word has been found, and we should return
  True
  .
• If the current position
  (i, j)
  is out of bounds or the character in the grid does not match the expected character in the word, return
  False
  .
3. Marking and Exploring :
• Temporarily mark the current cell as visited by changing its value to avoid revisiting it during the search.
• Explore the surrounding cells (up, down, left, right) by recursively calling the backtracking function with the next character position
  k+1
  .
• Restore the cell's original value after the exploration to backtrack correctly.
4. Iterative Exploration :
• Iterate over each cell of the grid, and for each cell, call the backtracking function starting with
  k=0
  to search for the word from that cell.
• If any of these calls return
  True
  , the word exists in the grid and the function should return
  True
  .
5. Result :
• If no starting cell leads to the entire word being formed, return
  False
  .

Detailed Steps in Pseudocode

                                            
# Initialize the main function
function wordSearch(board, word):
    # Define the backtracking function
    function backtrack(row, col, index):
        # If entire word is found
        if index == length(word):
            return True
        
        # If out of grid bounds or current character does not match the word's character
        if row < 0 OR row >= number of rows in board OR col < 0 OR col >= number of columns in board OR board[row][col] != word[index]:
            return False

        # Temporarily mark the cell as visited
        temp = board[row][col]
        board[row][col] = '/'

        # Explore all four possible directions
        found = backtrack(row + 1, col, index + 1) OR backtrack(row - 1, col, index + 1) OR backtrack(row, col + 1, index + 1) OR backtrack(row, col - 1, index + 1)

        # Restore the cell's original value after exploring
        board[row][col] = temp
        
        return found

    # Iterate over each cell in the grid
    for each row in range(number of rows):
        for each col in range(number of columns):
            # Begin the backtrack search from each cell
            if backtrack(row, col, 0):
                return True

    return False

                                        

Explanation

• Function
  wordSearch
  :
• Calls the
  backtrack
  function for each cell in the grid to start the search.
• If any call to
  backtrack
  returns
  True
  , the word exists in the grid and the function returns
  True
  .
• If no such path is found, it returns
  False
  .
• Function
  backtrack
  :
• Checks if the whole word is matched by comparing if
  index
  equals the length of the word.
• Ensures that the current coordinates
  (row, col)
  are within bounds and the current cell matches the corresponding character in the word.
• Marks the cell as visited by temporarily setting its value to
  '/'
  to prevent revisiting during this path search.
• Recursively explores in four directions (downwards, upwards, rightwards, leftwards).
• After the exploration, it restores the original value of the cell to ensure the grid remains unaltered for other paths.
• Returns
  True
  if any of the recursive calls match the remaining part of the word.

This highly detailed explanation and step-by-step pseudocode guide you in understanding how to tackle the encoding challenge.