StringProblem 23 of 43
Count of number of given string in 2D character array
Problem Statement
Given a 2D character array and a string word, count all occurrences of the given word in the 2D array. The word can be matched in all 8 directions: horizontally (left/right), vertically (up/down), and diagonally (4 diagonal directions).
Example:
- Input:
grid = [ ['G', 'E', 'E', 'K', 'S'], ['F', 'O', 'R', 'G', 'E'], ['E', 'K', 'S', 'E', 'E'], ['K', 'S', 'F', 'O', 'R'] ] word = "GEEKS" - Output:
4 - Explanation: "GEEKS" appears 4 times in the grid in different directions
Approach 1: Brute Force (Search All Directions)
Intuition
For each cell in the grid, try to match the word starting from that cell in all 8 possible directions. Count all successful matches.
Algorithm
- Define 8 directions: right, left, down, up, and 4 diagonals
- For each cell (i, j) in the grid
- For each direction, try to match the complete word
- If match found, increment count
- Return total count
java
public class Solution {
// 8 directions: R, L, D, U, DR, DL, UR, UL
private int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
private int[] dy = {1, -1, 0, 0, 1, -1, 1, -1};
private boolean search(char[][] grid, int row, int col,
String word, int dirX, int dirY) {
int R = grid.length, C = grid[0].length;
int len = word.length();
for (int k = 0; k < len; k++) {
int newRow = row + k * dirX;
int newCol = col + k * dirY;
// Check bounds
if (newRow < 0 || newRow >= R || newCol < 0 || newCol >= C) {
return false;
}
// Check character match
if (grid[newRow][newCol] != word.charAt(k)) {
return false;
}
}
return true;
}
public int countOccurrences(char[][] grid, String word) {
if (grid == null || grid.length == 0 || word == null || word.isEmpty()) {
return 0;
}
int R = grid.length, C = grid[0].length;
int count = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// Try all 8 directions from cell (i, j)
for (int d = 0; d < 8; d++) {
if (search(grid, i, j, word, dx[d], dy[d])) {
count++;
}
}
}
}
return count;
}
}Complexity Analysis
- Time Complexity: O(R * C * len * 8) = O(R * C * len) - For each cell, search in 8 directions, each taking O(len) time
- Space Complexity: O(len) - Recursion stack or temporary string storage
Approach 2: Optimized with Early Termination
Intuition
Same approach but with optimization: only search in a direction if the first character matches. This provides significant speedup in practice.
Algorithm
- Build a quick lookup for first character positions
- Only start searching from cells that match the first character of the word
- For each valid starting cell, search in all 8 directions
java
public class Solution {
private int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
private int[] dy = {1, -1, 0, 0, 1, -1, 1, -1};
private boolean search(char[][] grid, int row, int col,
String word, int dirX, int dirY) {
int R = grid.length, C = grid[0].length;
int len = word.length();
// Check if word can fit in this direction
int endRow = row + (len - 1) * dirX;
int endCol = col + (len - 1) * dirY;
if (endRow < 0 || endRow >= R || endCol < 0 || endCol >= C) {
return false;
}
for (int k = 0; k < len; k++) {
if (grid[row + k * dirX][col + k * dirY] != word.charAt(k)) {
return false;
}
}
return true;
}
public int countOccurrences(char[][] grid, String word) {
if (grid == null || grid.length == 0 || word == null || word.isEmpty()) {
return 0;
}
int R = grid.length, C = grid[0].length;
int count = 0;
char firstChar = word.charAt(0);
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// Only search if first character matches
if (grid[i][j] == firstChar) {
for (int d = 0; d < 8; d++) {
if (search(grid, i, j, word, dx[d], dy[d])) {
count++;
}
}
}
}
}
return count;
}
}Complexity Analysis
- Time Complexity: O(R * C * len * 8) - Worst case same as brute force, but much faster in practice
- Space Complexity: O(1) - Only constant extra space
Key Takeaways
- 8-directional search is a common pattern for 2D grid problems
- Direction vectors (dx, dy arrays) simplify code and reduce repetition
- Early termination by checking first character or bounds improves practical performance
- Boundary checking is critical - check before accessing grid cells
- This pattern extends to word search puzzles and similar grid-based string matching problems