Generate list of possible words from a character matrix

Given a M x N boggle board, find list of all possible words that can be formed by a sequence of adjacent characters on the the board.

We are allowed to search a word in all eight possible directions i.e. North, West, South, East, North-East, North-West, South-East, South-West, but a word should not have multiple instances of the same cell.

 
For example, consider below traditional 4 x 4 boggle board and a dictionary of valid words.

boggle board

Dictionary: { START, NOTE, SAND, STONED }

 
Output: The valid words are: { NOTE, SAND, STONED }

 
We can use DFS to solve this problem. The idea is to start from each character in the matrix and explore all eight paths possible and recursively check if they leads to a solution or not. To make sure that a word doesn’t have multiple instances of the same cell, we keep track of cells involved in current path in an matrix and before exploring any cell, we ignore the cell if it is already covered in current path.

To find all possible possible movements from a cell, we can use an array to store the relative position of movement from any cell. For example, if the current cell is (x, y), we can move to (x + row[k], y + col[k]) for 0 <= k <=7 using below array.

int row[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int col[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

So, from position (x, y), we can move to:

(x – 1, y – 1)
(x – 1, y)
(x – 1, y + 1)
(x, y – 1)
(x, y + 1)
(x + 1, y – 1)
(x + 1, y)
(x + 1, y + 1)

 
The algorithm can be implemented as follows in C++:

 

Download   Run Code

Output:

NOTE
SAND
STONED

 
The time complexity of above solution is exponential. We can improve the time complexity by using a trie data structure. The idea is to build a trie out of the given words and then perform pre-order traversal (DFS) on it as shown below:

 

Download   Run Code

Output:

STONED
NOTE
SAND

 
Thanks for reading.

Please use online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of