1

Word Search - lll

Difficulty: MEDIUM
Contributed By
Sounak Majumder
Avg. time to solve
20 min
Success Rate
80%

Problem Statement
Suggest Edit

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.
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.
Reset Code
Full screen
copy-code
Console