Word Search

class Solution {
private:
    vector<vector<char>> grid;
    int gridRows;
    int gridCols;
    
public:
    bool canFormWord(vector<vector<char>>& grid, string word) {
        this->grid = grid;
        gridRows = grid.size();
        gridCols = grid[0].size();
        for (int r = 0; r < gridRows; ++r)
            for (int c = 0; c < gridCols; ++c)
                if (searchDFS(r, c, word, 0)) return true;
        return false;
    }
    
protected:
    bool searchDFS(int r, int c, const string& word, int idx) {
        if (idx >= word.size()) return true;
        if (r < 0 || r == gridRows || c < 0 || c == gridCols ||
            grid[r][c] != word[idx])
            return false;
        bool found = false;
        grid[r][c] = '#';
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        for (int direction = 0; direction < 4; ++direction) {
            found = searchDFS(r + dx[direction], c + dy[direction], word, idx + 1);
            if (found) break;
        }
        grid[r][c] = word[idx];
        return found;
    }
};

The provided C++ program defines a solution to find if a given word can be formed in a 2D grid of characters. The Solution class implements a canFormWord method for checking word existence in the grid using DFS-based search and a helper searchDFS method.

1. Initialization: The Solution class is initialized with a private grid, gridRows, and gridCols to store the character grid and its dimensions.

2. Method - canFormWord: This method takes a 2D grid and a word as parameters. It sets the class's grid to the provided grid and calculates the number of rows and columns. It iterates over each cell in the grid, initiating a DFS search from any starting position if the first character matches.

3. Method - searchDFS: This protected helper function is used for the DFS search. It checks if the current index has reached the word's length, which means the word has been found. It also checks boundary conditions and whether the current grid cell matches the character at the current index of the word. The grid cell is temporarily marked to avoid revisiting during the current word search. A recursion is performed for all four possible directions (up, down, left, right). If the word is found via any recursive path, it breaks the loop and marks the search as successful. After exploring, the grid cell is restored to its original character to allow for other potential search paths.

4. Character marking and restoration: To avoid using extra memory for tracking visited cells during the DFS, the current character in the grid is replaced temporarily with a special character (e.g., '#'). After recursive exploration, the original character is restored for potential future searches.

By using depth-first search recursively and checking all possible paths for forming the word starting from each relevant cell, this method efficiently determines the existence of the word in the grid. Implementing the backtracking with marking and restoring characters within the grid ensures that no additional space is used for a visited array, optimizing the solution in terms of space complexity.

class WordSearch {
    private char[][] grid;
    private int height;
    private int width;
    
    public boolean canFind(char[][] grid, String target) {
        this.grid = grid;
        this.height = grid.length;
        this.width = grid[0].length;
    
        for (int i = 0; i < this.height; i++) {
            for (int j = 0; j < this.width; j++) {
                if (this.dfs(i, j, target, 0)) return true;
            }
        }
        return false;
    }
    
    private boolean dfs(int i, int j, String target, int idx) {
        if (idx >= target.length()) return true;
        if (
            i < 0 ||
            i == this.height ||
            j < 0 ||
            j == this.width ||
            this.grid[i][j] != target.charAt(idx)
        ) return false;
    
        boolean found = false;
        this.grid[i][j] = '#';
    
        int[] vertOffsets = {0, 1, 0, -1};
        int[] horizOffsets = {1, 0, -1, 0};
        for (int d = 0; d < 4; d++) {
            found = this.dfs(
                    i + vertOffsets[d],
                    j + horizOffsets[d],
                    target,
                    idx + 1
                );
            if (found) break;
        }
    
        this.grid[i][j] = target.charAt(idx);
        return found;
    }
}

The given Java class WordSearch provides a solution for checking if a target word can be found in a given 2D grid of characters. The solution employs depth-first search (DFS) to explore possible paths that match the characters of the target word. The class contains key components and functionalities outlined below:

• Attributes:

  • grid stores the character grid.
  • height and width maintain the dimensions of the grid.

• Methods:

  • canFind() initializes necessary attributes and iterates over the grid to start the search from every possible position. It returns true if a valid sequence forming the target word is found from any position.
  • dfs() is a recursive function that checks if continuing from a given cell leads to a solution. It uses the following checks and operations:
    • Base case of recursion which checks if the entire word has been successfully matched.
    • Boundary and character match conditions to ensure that the search stays within limits and follows the right path.
    • Marks the current grid cell to avoid revisiting during the current path search by temporarily changing its value.
    • Iterates in all four possible directions (up, down, left, right) and recursively attempts to find the word from each position.

Several aids assist in guiding and managing the search:

• vertOffsets and horizOffsets are arrays used for moving in the grid vertically and horizontally.
• After each recursive call, it restores the grid's character to enable new paths exploration.

The effective use of backtracking through marking the grid and recursion enables building and exploring possible paths that conform to the target word dynamically, making the implementation robust and optimized for problems involving searches in 2D spaces.

bool search(char** grid, int gridSize, int* gridColSize, char* target) {
    int MAX_ROWS = gridSize;
    int MAX_COLS = *gridColSize;
    bool dfs(int r, int c, char* remaining) {
        if (strlen(remaining) == 0) return true;
        if (r < 0 || r == MAX_ROWS || c < 0 || c == MAX_COLS ||
            grid[r][c] != remaining[0])
            return false;
            
        bool found = false;
        grid[r][c] = '#';
        int moves[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < 4; ++i) {
            found = dfs(r + moves[i][0], c + moves[i][1], remaining + 1);
            if (found) break;
        }
    
        grid[r][c] = remaining[0];
        return found;
    }
    
    for (int r = 0; r < MAX_ROWS; ++r) {
        for (int c = 0; c < MAX_COLS; ++c) {
            if (dfs(r, c, target)) return true;
        }
    }
    return false;
};

The provided C code defines a function search that determines if a target string can be found within a 2D grid of characters. The function utilizes depth first search (DFS) for its approach. Here's how the solution is structured and the logic it follows:

• Initialization of Grid Dimensions: The function starts by determining the maximum number of rows (MAX_ROWS) and columns (MAX_COLS) of the grid.

• DFS Function Definition: A nested function, dfs, is defined to handle the recursive search. This function will:

  • Check if the end of the target string is reached, returning true if so.
  • Validate the current position within grid boundaries and match the current grid cell with the current target character.
  • Mark the current grid cell to avoid revisiting in the current path by temporarily modifying its value.
  • Explore all possible directions (right, down, left, up) recursively.
  • Restore the grid cell's original value after exploring to allow for its revisitation in other potential paths.

• Exploration of Start Positions: The main function iterates over all possible starting positions in the grid, triggering the DFS search from each. If a complete path for the target string is found starting from any position, the function immediately returns true.

• Result: If no path is found after all possibilities have been explored, the function returns false, indicating the target string cannot be formed in the grid.

This implementation efficiently searches for the string while ensuring each cell in the grid can be part of different paths thanks to the marking and unmarking mechanism in the DFS process. By using DFS and a careful check of boundaries and character matches, the function can handle varying grid sizes and shapes.

var wordSearch = function (grid, target) {
    const MAX_ROWS = grid.length;
    const MAX_COLS = grid[0].length;
    const search = function (r, c, remaining) {
        if (remaining.length == 0) return true;
        if (
            r < 0 ||
            r == MAX_ROWS ||
            c < 0 ||
            c == MAX_COLS ||
            grid[r][c] != remaining.charAt(0)
        )
            return false;
        let result = false;
        grid[r][c] = "#";
        const moves = [
            [0, 1],
            [1, 0],
            [0, -1],
            [-1, 0],
        ];
        for (let [dr, dc] of moves) {
            result = search(r + dr, c + dc, remaining.slice(1));
            if (result) break;
        }
        grid[r][c] = remaining.charAt(0);
        return result;
    };
    
    for (let r = 0; r < MAX_ROWS; ++r) {
        for (let c = 0; c < MAX_COLS; ++c) {
            if (search(r, c, target)) return true;
        }
    }
    return false;
};

The provided JavaScript function wordSearch is designed to determine whether a given word (target) can be found in a 2D grid (grid) by moving horizontally or vertically. The solution employs a recursive approach to traverse the grid.

Functionality Breakdown:

• Define and initialize the maximum number of rows (MAX_ROWS) and columns (MAX_COLS) based on the grid's dimensions.
• Implement a helper function search that:
  • Checks if the current position is valid — it should not be out of grid bounds and must match the current character in target.
  • Recursively explores possible paths from the current position (right, down, left, up).
  • Temporarily marks the grid cell as visited by replacing it with #.
  • Restores the grid cell back to its original character after exploring to allow for other potential paths using backtracking.
• Iterate over each cell in the grid, starting the search for target from each cell utilizing the recursive function.
• Return true if the target is found, otherwise false.

Key considerations in this approach:

• Recursive depth is controlled by the length of target, making the solution efficient by stopping further exploration once the end of the word is reached.
• Backtracking ensures that exploring one path does not hinder the possibility of finding target through another path.
• This algorithm effectively handles cases of repeated characters in the grid by using a temporary character replacement strategy to mark visited cells.

By making use of recursive backtracking, the function efficiently explores all potential paths in the grid that might form the word target. This approach assures thorough examination while maintaining a manageable execution stack, making it suited for moderately sized grids and target words.

class Solution:
    def wordExists(self, matrix: List[List[str]], target_word: str) -> bool:
        self.ROWS = len(matrix)
        self.COLS = len(matrix[0])
        self.matrix = matrix
    
        for r in range(self.ROWS):
            for c in range(self.COLS):
                if self.search(r, c, target_word):
                    return True
    
        # after thorough search, no match found
        return False
    
    def search(self, r: int, c: int, remaining_suffix: str) -> bool:
        if len(remaining_suffix) == 0:
            return True
    
        if (
            r < 0
            or r == self.ROWS
            or c < 0
            or c == self.COLS
            or self.matrix[r][c] != remaining_suffix[0]
        ):
            return False
    
        result = False
        # mark current cell as visited
        self.matrix[r][c] = "#"
        for dR, dC in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            result = self.search(r + dR, c + dC, remaining_suffix[1:])
            if result:
                break
    
        # reset the cell to its original value
        self.matrix[r][c] = remaining_suffix[0]
    
        return result

The given Python 3 code provides a solution to determine if a specific word can be located in a 2D matrix of letters. The board allows sequential letters in the word to be adjacent to each other in either a horizontal or vertical direction, but not diagonally.

Outline and Explanation:

• The wordExists function iterates through each cell in the matrix and starts the search for the target word originating from that cell using the search helper function.
• search attempts to find the remaining part of the word by moving to adjacent cells recursively.
• Base cases handle:
  • The successful scenario where the entire word has been matched, indicated by having an empty suffix.
  • Out-of-bounds conditions or a mismatch between the matrix cell and the current character of the word suffix.
• The cell being visited is temporarily marked with a special character "#" to prevent revisiting it in the same word search path.
• Recursive calls are made to continue the search in each of the four cardinal directions (Right, Down, Left, Up).
• After exploration, the matrix cell is reset to its original value to allow other potential search paths.
• If any path returns true during the recursive search, the function returns true immediately, indicating the word exists in the matrix.

By modifying letters temporarily and then restoring them, the program efficiently manages state without requiring additional space for tracking visited positions. This technique ensures the solution leverages the matrix itself as the visitation record, optimizing space complexity.