In this article, we will be going through an interesting problem. Boggle is a word game where players race to find words hidden in a grid of letters. We are given an MxN board where each cell has some character in it.
Our task is to find all the possible words that can be formed by a sequence of characters and the word formed must all be present in the given dictionary. We are allowed to move to any cell in all e directions, but the only constraint is that a word should not have multiple instances of the same cell.
Example:
Boggle [][] =
[{'C', 'A', 'S'},
{'O', 'A', 'K'},
{'D', 'S', 'T'}];
Dictionary [][] = { DOGS, CAT , SKY , COW}
We can see that possible words formed are DOGS, CAT. There are two approaches to solve this problem. One is using DFS and the other is using Trie. Let’s discuss these approaches in detail.
Using DFS
In this approach, we go for a normal DFS search with backtracking for every word. In this approach, the entire matrix can be considered as a graph with each cell representing a node. Two cells are said to be connected by an edge if they share a common side or a common edge (which will be mentioned in the question).In this question, we are given to travel in all 8 directions from the adjacent cell hence common edge-sharing cells are also connected.
In DFS we explore adjacent cells first and we also keep a visited matrix to keep track of cells so that each cell is visited only once. A good practice of implementing DFS or BFS is to keep an array for directions.
We traverse in all eight possible directions for every character in the matrix and start forming words. Once we form a word we check if it exists in the dictionary or not. If it does we print is else we move forward. If at some instance we get a false return type then we backtrack from the current cell and also mark the current cell as not visited. Let us now look at the implementation of the problem.
We will be implementing three functions:
- is_present (str) – This will check if the word formed so far is present in the dictionary or not with the bool return type
- DFS_utility (I , j , str) – This is a recursive function to print all words in the dictionary
- DFS () – This is the primary function that will invoke the DFS_utility function
- isvalid(x,y) – whether a particular cell is valid or not
The character matrix (boggle), dictionary, direction vectors and visited array will be defined globally so that we can use it anywhere in our code.
int m,n;
char boggle [m][n];
bool visited[m][n];
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
bool is_present (string &str)
{
for (int i=0;i<dictionary.size();i++)
{
if (str.compare (dictionary[i]) ==0)
{
return true;
}
}
return false;
}
void DFS()
{
string str = "";
for (int i = 0; i< m; i++)
for (int j = 0; j < n; j++)
DFS_util (i, j, str);
}
bool isvalid(int x,int y)
{
if(x<0 || x>=m || y<0 || y>=n)
{
return false;
}
if(vis[x][y]==true)
{
return false;
}
return true;
}
void DFS_Util(int i, int j, string& str)
{
visited[i][j] = true;
str = str + boggle[i][j];
if (is_present(str))
cout<< str <<endl;
for(int k=0;k<8;k++)
{
int nx = i + dx[k];
int ny = j + ny[k];
if(isvalid(nx,ny))
{
DFS_Util(nx,ny,str);
}
}
str.erase(str.length() - 1);
visited[i][j] = false;
}
Now we will be discussing another approach using Trie.
Trie is a data structure having structure same has general tree data structures. A Trie is a special data structure used to store strings that can be visualised like a graph. They are used to represent the “Retrieval” of data and thus the name Trie. Here, each letter of the word is stored in a node having end =TRUE, which marks the end of the word. The structure of trie contains 26(a-z) children of each node.
A single node can have multiple words underneath it. The structure of the trie data structure in implementation is given as:
struct Trie
{
Trie * Child[26];
bool end;
Trie()
{
end=false;
for (int i=0;i<26;i++)
Child[i]=NULL;
}
};
For implementing the boggle search algorithm we will be first inserting all words present in the dictionary into our trie node and then we will only look for those characters that are child of root of our trie structure. We will be implementing 3 functions
- insert_into_trie () – To insert all words of the dictionary into our trie
- is_present () – To find all the words
- isvalid () – to check if some cell is valid or not
- find_words() – Prime function that will call is_present function to search for a word in dictionary
Here as well we will use the global boggle character matrix and visited array. Isvalid functions are also the same and also the direction vectors.
void insert_into_Trie(Trie* root, char *str)
{
int n = strlen(str);
Trie* node = root;
for (int i = 0; i < n; i++)
{
int index = char_int(Key[i]);
if (node->Child[index] == NULL)
node->Child[index] = new Trie();
node = node->Child[index];
}
node->leaf = true;
}
void is_present(Trie* root, int i, int j, string str)
{
if (root->leaf == true)
cout << str << endl;
if (isvalid(i, j, visited))
{
visited[i][j] = true;
for (int K = 0; K < 26; K++)
{
if (root->Child[K] != NULL)
{
char ch = (char)K + (char)'A';
for(int d=0;d<8;d++)
{
int nx = i + dx[d];
int ny = j + dx[d];
if(isvalid(nx,ny) && boggle[nx][ny]==ch)
{
is_present(root,nx,ny,str+ch);
}
}
}
}
visited[i][j] = false;
}
}
void find_words(char boggle[M][N], Trie* root)
{
Trie* node = root;
string str = "";
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (node->Child[char_int(boggle[i][j])])
{
str = str + boggle[i][j];
is_present(node->Child[char_int(boggle[i][j])], i, j, str);
str = "";
}
}
}
}
Time Complexity – O (4^(N^2)) in both the solutions
Space Complexity – O (N^2)
Check out our courses on our website.
By Mridul Kumar
