Word Search - lll

Moderate
0/80
Average time to solve is 20m
6 upvotes
Asked in companies
GoogleAmazonUber

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.
Hint

The given matrix or string can have a variety of 26 alphabets, can you think of a data structure to implement this.

Approaches (1)
Trie Solution
  • 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.

Time Complexity

O(8 ^ (N * M) + Q * |W|), where ‘N’ and ‘M’ are the number of rows and columns in the given matrix and ‘Q’ and |W| are the number of queries and size of each word in the query.

 

As we are storing all the word in the query, in a trie which take time of the order of O(Q * |W|). Also while searching for the words in trie, we try to consider all the 8 neighbouring cell, and in the worst case we traverse N * M cells, Hence this search will take time of the order of O(8 ^ (N * M)).

Space Complexity

O(N * M + Q * |W|), where ‘N’ and ‘M’ are the number of rows and columns in the given matrix and ‘Q’ and |W| are the number of queries and size of each word in the query. 

 

As we are making the table for marking whether a word is visited or not which takes memory of the order of O(N * M). And we are making trie to store words inside it, hence there are ‘Q’ words, having length |W|, hence this may end up taking Q * |W| memory.

Code Solution
(100% EXP penalty)
Word Search - lll
Full screen
Console