Word Search - lll

Moderate

0/80

Average time to solve is 20m

Contributed by

6 upvotes

Asked in companies

Problem statement

You are given character matrix of dimension N * M. Then you are given 'Q' queries, each query consists of a word 'W', and you have to tell whether it is possible to form word 'W' by choosing some adjacent characters from this matrix.

Note:

1. Two characters are said to be adjacent if they share a side or corner i.e. for a cell inside the matrix have 8 adjacent cells (if they exist).
2. One character in the matrix will not be considered twice for forming a word.
3. All the characters in the matrix and words consist only of uppercase English alphabets only.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains three space-separated integers 'N', 'M', and 'Q' denoting the number of rows in the matrix, the number of columns in the matrix, and the number of queries respectively.

The following 'N' lines contain 'M' characters each, denoting the characters in i’th row of the matrix.

The following 'Q' lines contain a string ‘W’ each, denoting the word to be searched in the matrix.

Output Format:

For each query print a single line containing ‘1’ if the word is present in the matrix and ‘0’ if the word is not present in the matrix in a separate line. For more clarity refer to sample test cases.

The output of each query will be printed in a separate line.

Note:

You don't have to print anything, it has already been taken care of. Just Implement the given function.

Constraints:

1 <= N * M <= 12
1 <= Q <= 100
1 <= |W| <= 20

Sample Input 1:

3 3 3
COD
ADE
RER
CODER
RADE
DONUTS

Sample Output 1:

1
1
0

Explanation of sample input 1:

In the matrix “CODER” can be found at [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3)] and “RADE” can be found at [(3, 1), (2, 1), (2, 2), (2, 3)]. But there is no way to find “DONUTS” in the matrix.

Sample Input 2:

2 2 2 
ZO
OM
ZOO
MOOD

Sample Output 2:

1
0

Explanation of sample input 2:

In the matrix “ZOO” can be found at [(1, 1), (1, 2), (2, 1)]. But “MOOD” can not be found in the matrix.

Console