Showing posts from December, 2018

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. 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 u…