The “Word Search” problem challenges you to determine if a word exists in a grid of letters. The word can be constructed by sequentially adjacent cells in the grid, where “adjacent” means horizontally or vertically neighboring. Each cell in the grid can be used only once per word. Imagine this as a treasure hunt where you search for a path that spells out a word in a crossword-like puzzle.
Optimal Algorithm and Data Structure
Algorithm: Depth-First Search (DFS) with Backtracking
Data Structure: The grid itself (no additional data structures required)
Why it works:
This algorithm fits because it efficiently explores all potential paths while ensuring that no cell is revisited during a single word traversal. The constraints of the problem (exploring paths and reverting state) naturally align with the backtracking pattern.
Characteristics of the Problem:
• Searching through a grid (matrix).
• Constraints on movement: only adjacent cells.
• Avoiding revisits and backtracking as necessary.
• Exploring multiple possibilities (tree of choices).
When to Use DFS with Backtracking:
• Problems involving grid traversal where decisions need to be reverted.
• Constraints on movement or usage (e.g., “use each cell once”).
• Multi-path exploration where pruning invalid paths saves computation.
Algorithm Steps
1. Iterate through all cells in the grid.
2. For each cell, invoke a recursive DFS function to search for the word.
3. In the DFS:
• If the entire word is found, return true.
• If the current cell is out of bounds or mismatched, return false.
• Temporarily mark the cell as visited.
• Explore all adjacent cells recursively.
• Backtrack by restoring the cell state.
4. If no path constructs the word, return false.
public class WordSearch {
public boolean exist(char[][] board, String word) {
// Iterate through each cell in the grid
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, 0, i, j)) { // Start DFS from the current cell
return true;
}
}
}
return false; // Word not found
}
private boolean dfs(char[][] board, String word, int index, int i, int j) {
if (index == word.length()) return true; // Word completely matched
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
return false; // Out of bounds or character mismatch
}
char temp = board[i][j]; // Save the current character
board[i][j] = '#'; // Mark as visited
// Explore all adjacent cells
boolean found = dfs(board, word, index + 1, i + 1, j) ||
dfs(board, word, index + 1, i - 1, j) ||
dfs(board, word, index + 1, i, j + 1) ||
dfs(board, word, index + 1, i, j - 1);
board[i][j] = temp; // Restore the character after exploring
return found;
}
}Step By Step Breakdown
Step 1: Iterate Over the Grid
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (dfs(board, word, 0, i, j)) {
return true;
}
}
}
return false; // Word not found- Loops through every cell in the gird.
- For each cell, calls the dfs method to attempt forming the word starting from that cell.
Step 2: Base Case – Word Match
if (index == word.length()) return true;- Checks if the entire word has been matched (index reaches the word’s length).
Step 3: Base Case 2 – Invalid Conditions
if (i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] != word.charAt(index)) {
return false;
}- Ensures the current cell is within bounds of the grid.
- Verifies that the current cell matches the corresponding character in the word.
Step 4: Mark the Current Cell as Visited
char temp = board[i][j]; // Save the current character
board[i][j] = '#'; // Mark as visited- Temporarily replaces the current cell’s character with ‘#’ to mark as visited.
- Saves the original character (temp) to restore it later.
Step 5: Explore All Adjacent Cells
boolean found = dfs(board, word, index + 1, i + 1, j) || // move down
dfs(board, word, index + 1, i - 1, j) || // move up
dfs(board, word, index + 1, i, j + 1) || // move right
dfs(board, word, index + 1, i, j - 1); // move left- Recursively calls dfs on the four possible adjacent cells
- The search continues with the next character in the word (index + 1)
Step 6: Backtrack
board[i][j] = temp; // Restore the character after exploring- Restores the original character of the call after all adjacent cells have been explored.
- Ensures the grid remains unaltered for subsequent searches starting from other cells.
Step 7: Return
return found;- Propagates the result of the search back up the recursive call stack.
Why This Code Works
This solution effectively uses DFS with backtracking to explore all possible paths while maintaining low space complexity. It adheres to LeetCode best practices by stopping early, using in-place marking, and providing clear modularity for initialization and recursion.
