Word Search Problem Statement

Given a two-dimensional grid of size N x M consisting of upper case characters and a string 'WORD', determine how many times the 'WORD' appears in the grid.

The 'WORD' can be formed starting from any grid cell, moving in any of the eight possible directions: horizontally left, horizontally right, vertically up, vertically down, and the four diagonals.

Input:

N = 5 M = 5 Grid: "AXYXB" "NIAXX" "AXNJN" "XNIXA" "JAXIX" WORD = "NINJA"

Output:

3

Example:

Explanation:

The word 'NINJA' is found 3 times in the grid.

Constraints:

1

Question

Word Search Problem Statement

Given a two-dimensional grid of size N x M consisting of upper case characters and a string 'WORD', determine how many times the 'WORD' appears in the grid.

The 'WORD' can be formed starting from any grid cell, moving in any of the eight possible directions: horizontally left, horizontally right, vertically up, vertically down, and the four diagonals.

Input:

N = 5
M = 5
Grid:
 "AXYXB"
 "NIAXX"
 "AXNJN"
 "XNIXA"
 "JAXIX"
WORD = "NINJA"

Output:

Example:

Explanation:

The word 'NINJA' is found 3 times in the grid.

Constraints:

1 <= N <= 10^3
1 <= M <= 10^3
1 <= N*M <= 10^6
2 <= WORD.size <= 10^3

Time Limit: 1 second

Note:

You do not need to handle printing, focus on implementing the logic to compute the result.

Accepted Answer

Count how many times a given word appears in a 2D grid by moving in any of the eight possible directions.

Iterate through each cell in the grid and check if the word can be formed starting from that cell in any of the eight directions.
Use recursion to explore all possible paths from a starting cell to form the word.
Keep track of visited cells to avoid revisiting the same cell in the same path.
Return the count of how many times the word can be formed in the grid.

Asked in Oyo Rooms