StringProblem 24 of 43
Search a Word in a 2D Grid of characters
Problem Statement
Given a 2D grid of characters and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
- Input:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED" - Output:
true - Explanation: The word "ABCCED" can be traced in the grid
Approach 1: Brute Force (DFS without optimization)
Intuition
Start from each cell and perform DFS to check if the word can be formed. For each cell, explore all 4 directions and backtrack if the path doesn't lead to a solution.
Algorithm
- For each cell (i, j) in the grid
- If cell matches first character, start DFS
- In DFS, mark current cell as visited
- Recursively check all 4 directions
- Backtrack by unmarking the cell
- Return true if word is found
java
public class Solution {
private int[] dx = {0, 0, 1, -1};
private int[] dy = {1, -1, 0, 0};
private boolean dfs(char[][] board, String word, int idx,
int row, int col, boolean[][] visited) {
if (idx == word.length()) {
return true;
}
int R = board.length, C = board[0].length;
// Check bounds and validity
if (row < 0 || row >= R || col < 0 || col >= C) {
return false;
}
if (visited[row][col] || board[row][col] != word.charAt(idx)) {
return false;
}
// Mark as visited
visited[row][col] = true;
// Explore all 4 directions
for (int d = 0; d < 4; d++) {
if (dfs(board, word, idx + 1, row + dx[d], col + dy[d], visited)) {
return true;
}
}
// Backtrack
visited[row][col] = false;
return false;
}
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || word == null || word.isEmpty()) {
return false;
}
int R = board.length, C = board[0].length;
boolean[][] visited = new boolean[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (dfs(board, word, 0, i, j, visited)) {
return true;
}
}
}
return false;
}
}Complexity Analysis
- Time Complexity: O(R * C * 4^len) - For each cell, DFS explores 4 directions at each step
- Space Complexity: O(R * C) - For visited array + O(len) recursion stack
Approach 2: Optimized DFS (In-place Marking)
Intuition
Instead of using a separate visited array, temporarily modify the board by replacing visited characters with a special marker. This saves space and potentially improves cache performance.
Algorithm
- Same DFS approach but modify board in-place
- Mark visited cell by changing its character to '#'
- Restore original character during backtracking
- Add pruning: check character frequency before starting
java
import java.util.*;
public class Solution {
private int[] dx = {0, 0, 1, -1};
private int[] dy = {1, -1, 0, 0};
private boolean dfs(char[][] board, String word, int idx,
int row, int col) {
if (idx == word.length()) {
return true;
}
int R = board.length, C = board[0].length;
// Check bounds and validity
if (row < 0 || row >= R || col < 0 || col >= C) {
return false;
}
if (board[row][col] != word.charAt(idx)) {
return false;
}
// Mark as visited
char temp = board[row][col];
board[row][col] = '#';
// Explore all 4 directions
for (int d = 0; d < 4; d++) {
if (dfs(board, word, idx + 1, row + dx[d], col + dy[d])) {
board[row][col] = temp;
return true;
}
}
// Backtrack
board[row][col] = temp;
return false;
}
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || word == null || word.isEmpty()) {
return false;
}
int R = board.length, C = board[0].length;
// Pruning: Check character frequency
Map<Character, Integer> boardCount = new HashMap<>();
Map<Character, Integer> wordCount = new HashMap<>();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
boardCount.merge(board[i][j], 1, Integer::sum);
}
}
for (char c : word.toCharArray()) {
wordCount.merge(c, 1, Integer::sum);
}
for (Map.Entry<Character, Integer> e : wordCount.entrySet()) {
if (boardCount.getOrDefault(e.getKey(), 0) < e.getValue()) {
return false;
}
}
// Start DFS from each cell
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (dfs(board, word, 0, i, j)) {
return true;
}
}
}
return false;
}
}Complexity Analysis
- Time Complexity: O(R * C * len) - With pruning and early termination
- Space Complexity: O(len) - Only recursion stack, no visited array
Key Takeaways
- DFS with Backtracking is the standard approach for path-finding in grids
- In-place marking saves space by modifying the board temporarily
- Character frequency pruning can eliminate impossible cases early
- Reversing the word when the last character is rarer optimizes search
- This is a classic LeetCode problem (Word Search) that tests backtracking skills
- Always restore state during backtracking to ensure correctness