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
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