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