Solution Explanation: Word Search

The problem asks to determine if a given word exists in a grid of characters. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically), and each cell can be used only once.

This is a classic graph traversal problem that can be solved efficiently using Depth-First Search (DFS) with backtracking.

Approach:

1. DFS with Backtracking: The core of the solution is a recursive DFS function. It explores all possible paths from a starting point in the grid, checking if they spell out the target word. Crucially, it uses backtracking to undo the changes made to the grid as it explores different branches of the search tree.

2. Base Cases:

   • If the current character index k in the word reaches the end (k == word.length - 1), it checks if the current grid cell matches the last character of the word. If it does, the word is found.
   • If the current grid cell doesn't match word[k], the path is invalid, so it returns false.

3. Recursive Step:

   • The current cell's character is temporarily marked as visited (e.g., changed to a special character like '0'). This prevents revisiting the same cell within a path.
   • The function recursively calls itself for the four adjacent cells (up, down, left, right).
   • If any of the recursive calls return true, it means the word was found along that path.
   • Backtracking: After the recursive call, the current cell is restored to its original character. This is crucial for exploring other paths.

4. Iteration over Starting Points: The main function iterates through every cell in the grid, using each as a potential starting point for the DFS search. If the DFS finds the word from any starting point, the function immediately returns true.

Time Complexity Analysis:

• The DFS function has a branching factor of at most 4 (four adjacent cells). In the worst case, it explores all possible paths. The depth of the recursion is the length of the word (k). Thus, the worst-case time complexity of the DFS function is O(4k).
• Since the DFS function is called for each cell in the grid (m x n), the overall time complexity is O(m * n * 4k). However, this is a worst-case scenario. In practice, many paths will be pruned early because of mismatches.

Space Complexity Analysis:

• The space complexity is dominated by the recursion stack in the DFS function. The maximum depth of the recursion stack is the length of the word (k). Therefore, the space complexity is O(k).
• Additionally, we use a visited array (optional, but can improve efficiency), which has a size of m x n. Therefore, the space complexity could also be considered O(m*n) depending on whether you use a visited array.

Code (Python):

def exist(board, word):
    rows, cols = len(board), len(board[0])
    
    def dfs(row, col, index):
        if index == len(word):
            return True  # Word found
        if row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] != word[index]:
            return False  # Out of bounds or mismatch
 
        temp = board[row][col] #Store the character
        board[row][col] = '#' #Mark as visited
 
        res = (dfs(row + 1, col, index + 1) or
               dfs(row - 1, col, index + 1) or
               dfs(row, col + 1, index + 1) or
               dfs(row, col - 1, index + 1))
        
        board[row][col] = temp #Backtrack: Restore the character
 
        return res
    
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False
 

The code in other languages (Java, C++, Go, TypeScript, JavaScript, Rust, C#) provided previously follows the same algorithmic approach, differing only in syntax and data structures used. They all efficiently solve the Word Search problem using DFS and backtracking.