JavaScript Program to Search a Word in a 2D Grid of Characters
In this article, we will solve a problem in which you are given a grid, with characters arranged in a two-layout(2D). You need to check whether a given word is present in the grid. A word can be matched in all 8 directions at any point. Word is said to be found in a direction if all characters match in this direction (not in zig-zag form). The 8 directions are, Horizontally Left, Horizontally Right, Vertically Up, Vertically Down, and 4 Diagonal directions.
Examples:
Input: characterGrid = [ ['G', 'E', 'E', 'K', 'S', 'F', 'O', 'R', 'G', 'E', 'E', 'K', 'S'], ['G', 'E', 'E', 'K', 'S', 'Q', 'U', 'I', 'Z', 'G', 'E', 'E', 'K'], ['I', 'D', 'E', 'Q', 'A', 'P', 'R', 'A', 'C', 'T', 'I', 'C', 'E']]; word = "Beginner" Output: pattern found at 0, 0 pattern found at 0, 8 pattern found at 1, 0
Approach: Using Nested Loops
- In this approach, we are considering all eight possible directions in a 2D grid that is Horizontally Left, Horizontally Right, Vertically Up, Vertically Down, and 4 Diagonal directions.
- It defines the grid’s dimensions in the form of numbers of rows and columns and arrays for direction (dx and dy).
- The ‘searchWord” function checks if the given word matches when starting from a specific grid position and moving in each of the eight directions.
- The
findPatternthe function scans the entire grid, considering each cell as a potential starting point for the word search. - When you run the code with a provided character grid, it looks for “Beginner” and “EEE” in the grid and prints the coordinates where these words are found.
Example:
// JavaScript program to search
// for a word in a 2D grid
// Define the number of rows
// and columns in the given grid
let numRows, numCols;
// Define arrays for
// searching in all 8 directions
let dx = [-1, -1, -1, 0, 0, 1, 1, 1];
let dy = [-1, 0, 1, -1, 1, -1, 0, 1];
// This function searches for a word in all
// 8 directions from a
// starting point (r, c) in the grid
function searchWord(grid, r, c, word) {
// If the first character of the word
// doesn't match with the
// starting point in the grid
if (grid[r] !== word[0])
return false;
let wordLength = word.length;
let directionIndex = 0;
// Search for the word in all 8 directions
// starting from (r, c)
while (directionIndex < 8) {
// Initialize the starting point
// for the current direction
let k, currentRow = r + dx[directionIndex];
let currentCol = c + dy[directionIndex];
// The first character is already
// checked, match the remaining characters
for (k = 1; k < wordLength; k++) {
// If out of bounds, break
if (currentRow >= numRows || currentRow < 0 ||
currentCol >= numCols || currentCol < 0)
break;
// If not matched, break
if (grid[currentRow][currentCol] !== word[k])
break;
// Move in a particular direction
currentRow += dx[directionIndex];
currentCol += dy[directionIndex];
}
// If all characters matched, the value of k must
// be equal to the length of the word
if (k === wordLength)
return true;
directionIndex++;
}
return false;
}
// Search for the given word in a given
// matrix in all 8 directions
function findPattern(grid, targetWord) {
// Consider every point as a
// starting point and search for the given word
for (let r = 0; r < numRows; r++) {
for (let c = 0; c < numCols; c++) {
if (searchWord(grid, r, c, targetWord))
console.log("Pattern found at " + r + ", " + c);
}
}
}
// Driver code
numRows = 3;
numCols = 13;
let characterGrid = [
['G', 'E', 'E', 'K', 'S', 'F', 'O',
'R', 'G', 'E', 'E', 'K', 'S'],
['G', 'E', 'E', 'K', 'S', 'Q', 'U', 'I', 'Z',
'G', 'E', 'E', 'K'],
['I', 'D', 'E', 'Q', 'A', 'P', 'R', 'A', 'C',
'T', 'I', 'C', 'E']
];
findPattern(characterGrid, "Beginner");
findPattern(characterGrid, "EEE");
Output
Pattern found at 0, 0 Pattern found at 0, 8 Pattern found at 1, 0 Pattern found at 0, 2 Pattern found at 0, 10 Pattern found at 2, 2 Pattern found at 2, 12
Time complexity: O(N^2 * M), where N is the number of rows, and M is the number of columns in the grid.
Space complexity: O(1), as the code uses a fixed amount of additional memory regardless of the grid’s size.
Depth-First Search (DFS)
Using Depth-First Search (DFS) to search a word in a 2D grid involves recursively exploring each cell’s neighbors (up, down, left, right) to match the word’s characters, marking cells as visited to avoid revisits, and backtracking if a path doesn’t lead to a solution.
Example: In this example The exist function uses DFS to search for the given word in a 2D board of characters. It marks visited cells, exploring adjacent ones until the word is found. The example correctly verifies the existence of “ABCCED” in the board, returning true.
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
const dfs = (i, j, k) => {
if (k === word.length) return true;
if (i < 0 || j < 0 || i >= rows || j >= cols || board[i][j] !== word[k]) return false;
const temp = board[i][j];
board[i][j] = '#'; // mark as visited
const found = dfs(i + 1, j, k + 1) ||
dfs(i - 1, j, k + 1) ||
dfs(i, j + 1, k + 1) ||
dfs(i, j - 1, k + 1);
board[i][j] = temp; // unmark
return found;
};
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}
const board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
];
const word = "ABCCED";
console.log(exist(board, word));
Output
true