Boggle Search Problem in Java
Given an M x N board with a single character in each cell, a dictionary, and a way to perform dictionary searches, find every word that can be created by putting neighboring characters together in a certain order. It should be noted that while we can go to any of the eight nearby characters, a word cannot have more than one instance of the same cell.
Example 1:
Input:
dictionary[] = {"READ", "JAVA", "GO", "ONLINE", "IN", "DIG"};
boggle[][] = { { 'D', 'I', 'G', 'O' },
{ 'I', 'A', 'K', 'T' },
{ 'N', 'V', 'E', 'H' },
{ 'J', 'A', 'V', 'R' } };
Output:
The following are the words present in dictionary
DIG
GO
IN
JAVA
READ
Approach: Depth-First Traversal
Each character should be considered as a starting point, and all words should be found that start with that character. With Depth First Traversal, all words beginning with a given character can be located. Beginning with each cell, we traverse in-depth first. In order to ensure that a cell is only taken into consideration once in a word, we maintain track of visited cells.
Implementation:
FileName: BoogleDepthFirst.java
import java.io.*;
import java.util.*;
public class BoogleDepthFirst
{
static final String dict[] = { "READ", "JAVA", "GO", "ONLINE", "IN", "DIG" };
static final int N = dict.length;
static final int m = 4, n = 4;
// A specified function to determine whether a specified string exists in the dictionary.
// The implementation is basic for ease of use. We are given a dictionary according to the query.
static boolean Word(String s)
{
// Search of all words linearly
for (int i = 0; i < N; i++)
if (s.equals(dict[i]))
return true;
return false;
}
// A function that iteratively prints every word found on Boggle
static void WordsFind(char boggle[][], boolean visit[][], int i,
int j, String s)
{
// Add the current character to s and mark the current cell as visited.
visit[i][j] = true;
s = s + boggle[i][j];
// If s is found in the dictionary, print it.
if (Word(s))
System.out.println(s);
// Traverse through 8 neighbouring boggle[i][j] cells.
for (int row = i - 1; row <= i + 1 && row < m; row++)
{
for (int col = j - 1; col <= j + 1 && col < n; col++)
{
if (row >= 0 && col >= 0 && !visit[row][col])
WordsFind(boggle, visit, row, col, s);
}
}
// Remove the current character from the string and indicate that the current cell was visited as false.
s = "" + s.charAt(s.length() - 1);
visit[i][j] = false;
}
// The words present in the dictionary are printed
static void findWords(char boggle[][])
{
// Make every character appear as unvisited.
boolean visit[][] = new boolean[m][n];
// Current string initialization
String s = "";
//consider each character and search for every word, beginning with this character.
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
WordsFind(boggle, visit, i, j, s);
}
}
}
public static void main(String args[])
{
char boggle[][] = { { 'D', 'I', 'G', 'O' },
{ 'I', 'A', 'K', 'T' },
{ 'N', 'V', 'E', 'H' },
{ 'J', 'A', 'V', 'R' } };
System.out.println("The following are the words present dictionary: ");
findWords(boggle);
}
}
Output:
The following are the words present dictionary:
DIG
GO
IN
JAVA
READ
Complexity Analysis:
The Time Complexity for the above approach is O(N2 *M2), where N and M represent the number of rows and columns. The Space Complexity is given by O(N*M).
Approach: Optimized Approach
We are able to execute a DFS on all words in the dictionary and determine whether we can make that word from the matrix or not, as opposed to creating all strings from the matrix and then determining whether they appear in the dictionary or not. This method is more optimized than the last one.
Implementation:
FileName: OptimisationBoggleSearch.java
import java.io.*;
import java.util.*;
public class OptimisationBoggleSearch
{
private static final int m = 3;
private static final int n = 3;
private static boolean dfsOptimal(char[][] mat, String s, int i, int j, int x, int y, int index)
{
//Check to see if the word can be created beginning at the present board position (i, j).
if (i < 0 || i >= x || j < 0 || j >= y )
{
return false;
}
if (s.charAt(index) != mat[i][j])
{
return false;
}
if (index == s.length() - 1)
{
return true;
}
char temp = mat[i][j];
mat[i][j] = '*';
boolean a = dfsOptimal(mat, s, i, j + 1, x, y, index + 1);
boolean b = dfsOptimal(mat, s, i, j - 1, x, y, index + 1);
boolean c = dfsOptimal(mat, s, i + 1, j, x, y, index + 1);
boolean d = dfsOptimal(mat, s, i - 1, j, x, y, index + 1);
boolean e = dfsOptimal(mat, s, i + 1, j + 1, x, y, index + 1);
boolean f = dfsOptimal(mat, s, i - 1, j + 1, x, y, index + 1);
boolean g = dfsOptimal(mat, s, i + 1, j - 1, x, y, index + 1);
boolean h = dfsOptimal(mat, s, i - 1, j - 1, x, y, index + 1);
mat[i][j] = temp;
return a || b || c || e || f || g || h || d;
}
private static void Boggle(char[][] mat, String[] dict)
{
int n = mat.length;
int m = mat[0].length;
// words found during the DFS traversal should be stored in both the answer and the store.
Set<String> answer = new HashSet<>();
Set<String> store = new HashSet<>();
// It starts from every cell on the board and iterates through every word in the dictionary,
// performing a DFS traversal for every word.
for (String s : dict)
{
int l = s.length();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// It adds it to the store if the word is located.
if (dfsOptimal(mat, s, i, j, n, m, 0))
{
store.add(s);
}
}
}
}
for (String i : store)
{
System.out.println(i);
}
}
public static void main(String[] args)
{
char boggle[][] = { { 'D', 'I', 'G', 'O' },
{ 'I', 'A', 'K', 'T' },
{ 'N', 'V', 'E', 'H' },
{ 'J', 'A', 'V', 'R' } };
String dict[] = { "READ", "JAVA", "GO", "ONLINE", "IN", "DIG" };
System.out.println("The following are the words present dictionary: ");
Boggle(boggle, dict);
}
}
Output:
The following are the words present dictionary:
READ
JAVA
DIG
IN
GO
Complexity Analysis:
The Time Complexity for the above approach is O(N*W + R*C^2), and the Space complexity is O(N*W + R*C).