Last Updated: 7 Jan, 2021

Word Boggle

Ninja

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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:

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.
Create a boolean visited matrix of size N x M and initialize all the cells to false.
Create an empty string let’s say curr.
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].
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):

Mark visited[i][j] as true.
Add the current character to the curr string, i.e. curr += mat[i][j]
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.
Then move in all 8 possible directions in the matrix mat recursively.
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.

Solve now

02 Approach

The idea is similar to the previous approach, but here instead of searching for each possible word from the starting of each cell in the matrix mat, we implement a trie data structure and insert all the elements from the array arr into the trie. Then, instead of starting the backtracking from each cell, we start the backtracking from all the children of the root of the trie those are present in the matrix mat. For example, if there are 3 children of the root in the trie, i.e. ‘a’, ‘b’ and ‘c’, then we start the backtracking only from those cells in the matrix mat, that contains the character ‘a’, ‘b’ and ‘c’ only.

Steps:

Implement the trie and insert all the words from the array arr into it.
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.
Create a boolean visited matrix of size N x M and initialize all the cells to false.
Run a nested loop with the outer loop running from i = 0 to N and the inner loop running from j = 0 to M, and do:
1. If the character at mat[i][j] is a child of the root of the trie, then add this character to the curr string.
2. Call the backtracking function possibleWordsUtil(root->children[mat[i][j]], mat, visited, i, j, n, m, curr, st).
3. Make the curr string empty again.
After this, 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(root, mat, visited, i, j, n, m, curr, st):

If the current root is a leaf of the trie, then insert the curr string in to the set st.
Mark visited[i][j] as true.
Then move in all 8 possible directions in the matrix mat and if the character at any of the adjacent cell is present as the child of the root, then call the function recursively by adding the character to the curr string.
Finally, make visited[i][j] = false at the end of the function.

Solve now