Find All Occurrences in Matrix

You are provided with a matrix of characters, CHARACTER_MATRIX of size M x N, and a string WORD. Your goal is to locate and display all occurrences of the string within the matrix. The search for the string can be conducted in all eight possible directions: North, South, East, West, North-East, North-West, South-East, and South-West.

Input:

The first line of input contains two space-separated integers 'M' and 'N' indicating the dimensions of the matrix 'CHARACTER_MATRIX'.
Next M lines contain N space-separated characters denoting the elements of the matrix.
The following line contains the string WORD.

Output:

For each occurrence, print the coordinates of each character in the format:
‘FIRST_CHARACTER’(X1, Y1) ‘SECOND_CHARACTER’(X2, Y2) ...
If no occurrences are found, output 'No match found'.

Example:

Input:
[ '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' ]
WORD = "CODE"
Output:
'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)

Constraints:

  • 1 <= M, N <= 100
  • 1 <= WORD LENGTH <= 5
  • Time Limit: 1 sec

Note:

Your implementation function does not need to print anything. It's already handled.
AnswerBot
6d

Find all occurrences of a given string in a matrix in all eight possible directions.

  • Iterate through each cell in the matrix and check for the starting character of the word.

  • For each starting character...read more

Help your peers!
Add answer anonymously...
Paytm Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter