You are given a grid of letters, followed by some words. The words can occur anywhere in the grid on a row or a column, forward or backwards. However, there are no diagonal words. Write an algorithm to find if the given word occurs in the grid on a row or a column, forward or backwards.
Input
The first line of input consists of two integers- grid_row and grid_col, representing the number of rows (N) and the number of columns (M) of the letter grid, respectively.
The next M lines consist of N space-separated characters representing the letters of the grid
The next line consists of an integer- word_size, representing the number of words to be searched from the given grid (K)
The last line consists of K space-separated strings representing the words to search for in the grid.
Output
Print K space-separated strings consisting of "Yes" if the word is present in the grid or "No" if the word is not present in the grid.
Note
All the inputs are case-sensitive, meaning "a" and "A" are considered as two different characters.
Example 1:
Input: grid = [['C', 'A', 'T'], ['I', 'D', 'O'], ['N', 'O', 'M']], words = ["CAT", "TOM", "ADO", "MOM"]
Output: ["Yes", "Yes", "Yes", "No"]
Explanation:The word "CAT" is present in the first row of the grid.
The word "TOM" is present in the third column of the grid, backwards.
The word "ADO" is present in the second column of the grid.
The word "MOM" is not present in the grid.
TO-DO
input:
output: