Find all occurrences

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)

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.

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)

'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)

Consider the first line of output: (I) The first character of string i.e. 'C' is present in row 2 column 2. (II) Second character 'O' is present in row 1 and column 1. (III) Third character 'D' is present in row 0 and column 0. (IV) Last character 'E' is present in row 0 column 1. Similarly, other lines of output can be understood.

DFS

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.

Time Complexity

O(M * N * (8 ^ L)), Where ‘M’ * ‘N’ is the size of the matrix and ‘L’ is the length of string.

Since we’ll be traversing all the elements present in the matrix, ‘ARR’ and for every character in the string, we’ll have 8 directions to go. Thus the time complexity will be O(M * N * (8 ^ L)).

Space Complexity

O(M * N), Where ‘M’ * ‘N’ is the size of the matrix.

Since stack space is involved in recursion. Thus the space complexity will be O(M * N).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of Sample Output 1:

Sample Input 2:

Sample Output 2:

Explanation of Sample Output 2: