Word Search - lll - Coding Ninjas

New update is available. Click here to update.

Last Updated: 16 Jan, 2021

Word Search - lll

Moderate

Solve now

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.

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

Solve now

Approaches

01Approach

Make a Trie, which stores 26 pointers to next characters each representing a English Alphabet. Also at each node store a list wordEndingHere, representing the index of the query-word which ends here.
Insert all the queries inside this trie.
Make a two dimensional matrix ‘visited’, which represents if the current cell is visited or not in the given matrix. And mark all the cells as unvisited in the matrix.
Make a recursive function which will take in the Root of the Trie formed, matrix current position coordinates and ‘visited’ table.
Base condition for this function is when all the neighbouring elements of the current cell are already visited or they don’t exist. In that case we have no way to move ahead and simply return.
For each call, we mark all the queries whose index are present in the wordEndinghere list stored in the current node of the trie as found.
In the cases where base condition is not satisfied:
- Mark the current cell as visited, so that it won’t be included again in the search of the words.
- Match each possible unvisited neighbouring cell in the matrix with the sub trie of the given root of the trie. If they exist, call this recursive function again, in the search to find only queried words.
- After exploring all the neighboring cells of the current cell, mark the current cell as unvisited, so that in other ways of searching, this letter can be included.
Go through the given matrix, wherever we find that sub-trie corresponding to that character is not null we call the above recursive function which will help to mark all the queried words present in the matrix.
This way we only traverse through the words which are present in the trie, and in the end we will mark all the present words in the matrix.

For example:-

Let’s say we have a matrix as follows:

And words that need to be searched are ZOOM, ZOO, MOOD.

So trie for these words will look like this:-

Following the above algo,rithm we just need to pick those cells in the matrix where the character is Z or M. Then use that cell as the starting position and start looking for the next character in the trie, from the neighbour of that cell in the matrix.

In the given matrix we start at location (1, 1) where Z is located, then we just need to go towards that direction where the next character will be O and that is an unvisited cell only. As there is only one sub-trie of Z. By which we can reach location (1, 2) or (2, 1). While moving to these locations we mark (1, 1) as visited. Again start the search from that point.

Also while moving to any new cell, first mark the queries at index present in wordEndingHere list present in that trie node.

This way, queries like ZOO and ZOOM can be searched simultaneously.

Solve now