Word Boggle

Ninja
0/200
Average time to solve is 16m
14 upvotes
Asked in companies
WalmartGoogle inc

Problem statement

You are given an array of strings “arr” and a character matrix “mat”. Your task is to find out all the possible words in the array “arr” that can be constructed by moving sequentially in the matrix “mat”, where the movement can start from any position in the matrix “mat” and can be done in all 8 possible directions. However, the same cell can not be considered more than once for the construction of a word. Print the words in sorted manner.

For Example: 
If arr = {“go”, “pp”, “no”, “op”}, mat = {{‘g’,’p’}, 
                                          {‘d’,’o’}}.
Here, the two-letter words that can be formed from the matrix “mat” are “gp”, “gd”, “go”, “pg”, “pd”, “po”, “dg”, “dp”, “do”, “og”, “op”, “od”.

So, the words that are present in the array “arr” which can be formed from the matrix “mat” are “go” and “op”.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains an integer P, denotes the length of the array.
The second line of each test case contains, P space separated strings.
The third line of each test case contains two space separated integers N, and M, denoting the number of rows and columns in a 'mat”.
The next N lines contain M characters i.e. the elements of the matrix “mat”.
Output format: 
For each test case, print all the possible words in the array “arr” in a sorted manner, that can be constructed by moving sequentially in the matrix “mat”.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= P <= 10
1 <= arr[i].length <= 50
1 <= N, M <= 7
All the characters of the strings in the array “arr” and matrix “mat” contain lowercase English letters only.
All the words in the array “arr” are unique.

Time limit: 1 second
Sample Input 1:
1
6
go on no of pon pgp
2 2
g n
o p
Sample Output 1:
go no on pon
Explanation for sample 1:
For the first test case, the word “go” can be formed by (0,0) → (1,0).
The word “on” can be formed by (1,0) → (0,1).
The word “no” can be formed by (0,1) → (1,0).
The word “of” can never be formed as there is no ‘f’ character in the matrix.
The word “pon” can be formed by (1,1) → (1,0) → (0,1).
The word “pgp” can not be formed as there is only one ‘p’ character in the matrix.
Sample Input 2:
1
8
person so warm on code no son rn  
2 3
p e r
n o s
Sample Output 2:
no on person so son
Explanation for sample 2:
For the first test case, the word “person” can be formed by (0,0) → (0,1) → (0,2) → (1,2) → (1,1) → (1,0).
The word “so” can be formed by (1,2) → (1,1).
The word “warm” can never be formed as there is no character ‘w’ in the matrix.
The word “on” can be formed by (1,1) → (1,0).
The word “code” can never be formed as there is no character ‘c’ in the matrix.
The word “no” can be formed by (1,0) → (1,1).
The word “son” can be formed by (1,2) → (1,1) → (1,0).
The word “rn” can not be formed as the character ‘r’ and ‘n’ are not adjacent to each other.
Hint

Think of a brute-force solution using backtracking.

Approaches (2)
Brute-force

The idea here is to start the search from every cell of the matrix mat and find all possible words that can be formed starting from this character using Backtracking. While doing so, we also keep a visited matrix and each time we visit a cell, we mark this cell as visited in the visited matrix, so that we do not consider the same character again and again while doing the traversal.

Steps:

  1. Create an empty set let’s say st, which will store all the possible words in the arr that can be formed from the mat by moving sequentially.
  2. Create a boolean visited matrix of size N x M and initialize all the cells to false.
  3. Create an empty string let’s say curr.
  4. Run a nested loop with the outer loop running from i = 0 to N-1 and the inner loop running from j = 0 to M-1, and do:
    1. Call a function let’s say possibleWordsUtil(mat, arr, visited, i, j, n, m, curr, st). This function will store all the possible words in the array arr that can be formed by moving sequentially starting from the mat[i][j].
  5. Then, create an empty array let’s say res and add all the words from the set st to this res array. As, the elements in a set are already sorted, so we finally return the res array.

void possibleWordsUtil(mat, arr, visited, i, j, n, m, curr, st):

  1. Mark visited[i][j] as true.
  2. Add the current character to the curr string, i.e. curr += mat[i][j]
  3. If the curr string matches with any of the word from the array arr, then add this to the set st. Note that, here we do not need to worry about multiple occurrences of the same word as we are storing the words in a set.
  4. Then move in all 8 possible directions in the matrix mat recursively.
  5. In the last step, as we are leaving a cell, remove the last character from the string curr and mark visited[i][j] as false.
Time Complexity

O(N*M * (8 ^ (N*M))), where N and M are the number of rows and columns in the matrix “mat” respectively.

In the worst case, for each cell in the matrix mat, we will be traversing in 8 possible directions in the whole matrix. So, for each cell, it takes 8 ^ (N * M) time and as there are (N ^ M) cells in the matrix, hence, the overall time complexity becomes O(N*M * (8 ^ (N*M))).

Space Complexity

O(N * M), where N and M are the number of rows and columns in the matrix “mat” respectively.

In the worst case, extra space is required for recursive calls, and also we are using a visited matrix of size (N * M) to keep track of the visited cells. Hence, the space complexity will be O(N * M).

Code Solution
(100% EXP penalty)
Word Boggle
Full screen
Console