Word Search - ll

Moderate
0/80
Average time to solve is 30m
11 upvotes
Asked in companies
SamsungUberOYO

Problem statement

You are given a two-dimensional grid having 'N' rows and 'M' columns, consisting of upper case characters. You are also given a word 'WORD'. You have to find the number of occurrences of that word in the grid.

Starting from a given cell, a word can be formed by moving in all eight directions: horizontally left, horizontally right, vertically up, vertically down, and four diagonal directions.

Example : 
There are three occurrences of the word 'NINJA' in the following grid:

word_grid

Note : 
1) Given word will not be a single character.

2) If occurrences of the given word start from two different cells, then these two occurrences are considered to be different.

Consider the word 'XYX' to be searched in the string 'AXYXB'. Here, we find an occurrence of 'XYX' at index 2 going in the right direction, and another occurrence at index 4 going in the left direction.

Although these two words correspond to the same word, they will be considered as different occurrences.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first input line contains two integers, 'N' and 'M', the number of rows and columns respectively.

The next 'N' input lines representing the rows of the grid, contain a string each of length 'M'.

The next input line contains a string 'WORD'.
Output Format : 
In the only output line prints the number of occurrences of the given string in the grid.
Note : 
You don't have to print anything. It has already been taken care of, just implement the given function.
Constraints : 
1 <= N <= 10^3
1 <= M <= 10^3
1 <= N*M <= 10^6
2 <= WORD.size <= 10^3

Time Limit : 1 sec
Sample Input 1 :
5 5
AANIQ
PJINT
NINJA
BLJIJ
PRADN
NINJA
Sample Output 1 :
3
Explanation For Sample Input 1 :

word_grid

Sample Input 2 :
3 4
RIAN
IAIR
AIRI
AIR
Sample Output 2 :
5
Hint

From each cell, try moving in all 8 directions as long as the string matches.

Approaches (2)
Brute Force

In thie approach we try to traverse in all directions when we found a matching character.

 

Here is the algorithm :

 

  1. Let’s do this : for each cell, we first check if the character in this cell matches the first letter of the given word. If not, then there lies no point in checking all eight directions, so we go to the next cell.
  2. To move in all eight directions, we create two arrays dx[] and dy[], which corresponds to the representation of these 8 directions in the X and Y axes respectively. Our implementation becomes much easier with this, we simply have to iterate over these arrays to move in all eight directions.
  3. The rest of the implementation is simple. Keep going in a particular direction as long as the string matches. If you find a mismatch, simply break and start looking in other directions. If you reach the end of the given word, you have found an occurrence of the word in the grid, so add 1 to the answer.
Time Complexity

O(N*M*X), where ‘N’ and ‘M’ are the number of rows and columns of the grid, and ‘X’ is the length of the given word.

 

There are N*M cells to consider, and for each cell, we go till a distance ‘X’ in the worst case for all eight directions. Hence, the overall time complexity will be O(N*M*X).

Space Complexity

O(1)

 

We are not using any extra space. Hence, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Word Search - ll
Full screen
Console