Count occurrences of a given word in a 2-D array in Java
Count occurrences of a given word in a 2-D array in Java
The following article demonstrates how to implement a Java method that scans through each element of a 2D array and counts the number of times a specified word appears. The word can be formed by moving in any of the four cardinal directions (up, down, left, right) and can also bend 90 degrees. Each cell can be used only once per word formation. The above skill is useful for solving complex problems involving multidimensional data structures and is essential for data analysis, text processing, and pattern recognition.
Example:
Input:
a = {
{'H', 'E', 'L', 'L', 'O'},
{'E', 'H', 'L', 'L', 'O'},
{'L', 'E', 'H', 'L', 'O'},
{'L', 'L', 'L', 'H', 'O'},
{'O', 'O', 'O', 'O', 'H'}
}
str = "HELLO"
Output: 2
Explanation: The string "HELLO" appears 2 times in the matrix.
Using the Brute-force approach:
Algorithm
Step1: Set up a 2D grid of characters.
Step2: Define the word to search for.
Step 3: Iterate through each cell in the grid, checking all 8 possible directions for the word.
Step 4: Start from the current cell, check each character, ensure the new position is within bounds, verify the match, move to the next cell, and increment the count if all match.
Step5: Print the total count of occurrences of the word in the grid.
Here is an implementation to count occurrences of a given word in a 2-D array using a brute-force approach :
FileName:WordSearch.java
public class WordSearch {
public static void main(String[] args) {
char[][] grid = {
{'H', 'E', 'L', 'L', 'O'},
{'E', 'H', 'L', 'L', 'O'},
{'L', 'E', 'H', 'L', 'O'},
{'L', 'L', 'L', 'H', 'O'},
{'O', 'O', 'O', 'O', 'H'}
};
String word = "HELLO";
System.out.println("Count: " + countOccurrences(grid, word));
}
// Method to count the total occurrences of the word in the grid
public static int countOccurrences(char[][] grid, String word) {
int count = 0;
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
count += searchWord(grid, word, i, j, rows, cols);
}
}
return count;
}
// Method to search for the word starting from a specific cell in all 8 directions
public static int searchWord(char[][] grid, String word, int x, int y, int rows, int cols) {
int[] xDir = {0, 0, 1, -1, 1, -1, 1, -1};
int[] yDir = {1, -1, 0, 0, 1, -1, -1, 1};
int wordLen = word.length();
int count = 0;
for (int dir = 0; dir < 8; dir++) {
int k, newX = x, newY = y;
for (k = 0; k < wordLen; k++) {
// Check if the new position is out of bounds
if (newX >= rows || newX < 0 || newY >= cols || newY < 0) {
break;
}
// Check if the character does not match
if (grid[newX][newY] != word.charAt(k)) {
break;
}
// Move to the next cell in the current direction
newX += xDir[dir];
newY += yDir[dir];
}
// If all characters in the word are found in the direction, increment the count
if (k == wordLen) {
count++;
}
}
return count;
}
}
Output:
Count: 2
Complexity analysis: The above approach has a time complexity of O({rows} * {cols}) and a space complexity of O(1). It uses countOccurrences and searchWord methods, which iterate through each cell in the grid, resulting in a total time complexity of O({rows} {cols} {wordLen}) respectively.