Last Updated: 17 Nov, 2020

Find all occurrences

Moderate

Asked in companies

Solve now

Problem statement

You are given a 'M' x 'N' matrix of characters, 'CHARACTER_MATRIX' and a string 'WORD'. Your task is to find and print all occurrences of the string in the given character matrix. You are allowed to search the string in all eight possible directions, i.e. North, South, East, West, North-East, North-West, South-East, South-West.

Note: There should not be any cycle in the output path. The entire string must lie inside the matrix boundary. You should not jump across boundaries, i.e. from row 'N' - 1 to 0 or column 'N' - 1 to 0 or vice versa.

Example:

Consider below matrix of characters,
[ 'D', 'E', 'X', 'X', 'X' ]
[ 'X', 'O', 'E', 'X', 'E' ] 
[ 'D', 'D', 'C', 'O', 'D' ]
[ 'E', 'X', 'E', 'D', 'X' ]
[ 'C', 'X', 'X', 'E', 'X' ]

If the given string is "CODE", below are all its occurrences in the matrix:

'C'(2, 2) 'O'(1, 1) 'D'(0, 0) 'E'(0, 1)
'C'(2, 2) 'O'(1, 1) 'D'(2, 0) 'E'(3, 0)
'C'(2, 2) 'O'(1, 1) 'D'(2, 1) 'E'(1, 2)
'C'(2, 2) 'O'(1, 1) 'D'(2, 1) 'E'(3, 0)
'C'(2, 2) 'O'(1, 1) 'D'(2, 1) 'E'(3, 2)
'C'(2, 2) 'O'(2, 3) 'D'(2, 4) 'E'(1, 4)
'C'(2, 2) 'O'(2, 3) 'D'(3, 3) 'E'(3, 2)
'C'(2, 2) 'O'(2, 3) 'D'(3, 3) 'E'(4, 3)

Input Format :

The first line of input contains two space-separated integers 'M' and 'N representing the size of the 2D matrix 'CHARACTER_MATRIX'.

Next M lines contain N single space-separated characters representing the matrix elements.

Next line contains a string WORD.

Output Format :

For each test case, print the coordinates of each character of the string.

Print the output of each occurrence in a separate line in the format:
‘FIRST_CHARACTER’(X1, Y1) ‘SECOND_CHARACTER’(X2, Y2) ...

If no occurrence is found print 'No match found' (without quotes)

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= M, N <= 100
1 <= WORD LENGTH <= 5

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We can use DFS to solve this problem. The idea is to start from each cell in the matrix and explore all eight paths possible and recursively check if they will lead to the solution or not. To make sure that the path is simple and doesn’t contain any cycles, we keep track of cells involved in the current path and before exploring any cell, we ignore it if it is already covered in the current path.

We can find all the possible locations we can move to from the given location by using the array that stores the relative position of movement from any location.

For example, if the current element is ‘ARR[R, C]’, we have to search among the following elements:

‘ARR[R-1, C-1]’
‘ARR[R-1, C]'
‘ARR[R-1, C+1]’
‘ARR[R, C-1]’
‘ARR[R, C+1]’
‘ARR[R+1, C-1]’
‘ARR[R+1, C]’
‘ARR[R+1, C+1]’

So, we can create a helper array to store relative positions of elements that we’ll be exploring.

‘ROW[]’ = {-1, -1, -1, 0, 0, 1, 1, 1}

'COL[]' = {-1, 0, 1, -1, 1, -1, 0, 1}

Now, once we have identified the relative positions we’ll iterate through the ‘ROW[i]’ and ‘COL[i]' arrays, for each 0 <= ‘i’ < 8 and :

Check if the current position is valid or not. Any position ('ROW[i]', ‘COL[i]’) is valid iff:
1. 0 <= ‘ROW[i]’ < ‘M’
2. 0 <= 'COL[i]' < 'N'
3. ('ROW[i]', ‘COL[i]’) should not be present in the current path
Recursively check for the next character of ‘WORD’ and store.

Whenever you reach the end of string ‘WORD’ print the path stored.

Solve now