How to useNested Loops in Javascript
- 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
findPattern
the 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 “GEEKS” 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, "GEEKS");
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.
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 = "GEEKS" Output: pattern found at 0, 0 pattern found at 0, 8 pattern found at 1, 0