How To 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++:


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:




Popular posts from this blog

8 Machine Learning Algorithms explained in Human language

Deep Learning Architectures explained in Human Language

How To Set Up Pokemon MMO: