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.

JavaScript
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

Similar Reads

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

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