Find all possible words from board

We have been given a dictionary of words and a board of characters from which we can form strings. Now, we have to check if the string is present in the dictionary or not. We have to return the words which are present in the dictionary.

 Input:  dictionary[] = {"JAVA", "PYTHON", "HERO", "GO"}

       boggle[][]   = { { 'H', 'I', 'O' },

                                { 'A', 'E', 'R' },

                                { 'J', 'V', 'A' } };

   isWord(str): returns true if str is present in dictionary

                   else false.

Output:        Following words of dictionary are present

                          HERO

                          JAVA

Concept behind the solution

 Here, we will use the concept of depth first traversal. We will check if a character can be a starting of a word in dictionary or not. In this way, every character will be traversed. The time complexity of this algorithm is O(n^2*m^2). Here n and m is row and column size of matrix.

Code:

// C++ program to find words in dictionary from board of characters

#include <cstring>
#include <iostream>
using namespace std;


#define M 3
#define N 3
string dictionary[] = { “HERO”, “JAVA”, “PYTHON”, "GO" };
int n = sizeof(dictionary) / sizeof(dictionary[0]);
bool isWord(string& str)
{
	for (int i = 0; i < n; i++)
		if (str.compare(dictionary[i]) == 0)
			return true;
	return false;
}
void findWordsUtil(char boggle[M][N], bool visited[M][N], int i,
				int j, string& str)
{
	visited[i][j] = true;
	str = str + boggle[i][j];
	if (isWord(str))
		cout << str << endl;
	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 && !visited[row][col])
				findWordsUtil(boggle, visited, row, col, str);
	str.erase(str.length() - 1);
	visited[i][j] = false;
}
void findWords(char boggle[M][N])
{
	bool visited[M][N] = { { false } };
	string str = "";
	for (int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
			findWordsUtil(boggle, visited, i, j, str);
}
int main()
{
	char boggle[M][N] = { { ‘H’, ‘I’, ‘O’ },
						{ ‘A’, ‘E’, ‘R’ },
						{ ‘J’, ‘V’, ‘A’ } };


	cout << "Following words of dictionary are present\n";
	findWords(boggle);
	return 0;
}

// JAVA program to find words in dictionary from board of characters

class bn {
	static final String dictionary[] = { “HERO”, “JAVA”, “PYTHON”, "GUQ", "EE" };
	static final int n = dictionary.length;
	static final int M = 3, N = 3;
	static boolean isWord(String str)
	{
		for (int i = 0; i < n; i++)
			if (str.equals(dictionary[i]))
				return true;
		return false;
	}
	static void findWordsUtil(char boggle[][], boolean visited[][], int i,
							int j, String str)
	{
		visited[i][j] = true;
		str = str + boggle[i][j];
		if (isWord(str))
			System.out.println(str);
		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 && !visited[row][col])
					findWordsUtil(boggle, visited, row, col, str);
		str = "" + str.charAt(str.length() - 1);
		visited[i][j] = false;
	}
	static void findWords(char boggle[][])
	{
		boolean visited[][] = new boolean[M][N];
		String str = "";
		for (int i = 0; i < M; i++)
			for (int j = 0; j < N; j++)
				findWordsUtil(boggle, visited, i, j, str);
	}
	public static void main(String args[])
	{
		char boggle[][] = { { ‘H’, ‘I’, ‘O’ },
							{ ‘A’, ‘E’, ‘R’ },
							{ ‘J’, ‘V’, ‘A’ } };


		System.out.println("Following words of dictionary are present");
		findWords(boggle);
	}
}

# Python program to find words in dictionary from board of characters

dictionary = [“HERO”, “JAVA”, “PYTHON”, "GO"]
n = len(dictionary)
M = 3
N = 3
def isWord(Str):
	for i in range(n):
		if (Str == dictionary[i]):
			return True
	return False
def findWordsUtil(boggle, visited, i, j, Str):
	visited[i][j] = True
	Str = Str + boggle[i][j]
	
	if (isWord(Str)):
		print(Str)
	
	row = i - 1
	while row <= i + 1 and row < M:
		col = j - 1
		while col <= j + 1 and col < N:
			if (row >= 0 and col >= 0 and not visited[row][col]):
				findWordsUtil(boggle, visited, row, col, Str)
			col+=1
		row+=1
	
	Str = "" + Str[-1]
	visited[i][j] = False
def findWords(boggle):
	visited = [[False for i in range(N)] for j in range(M)]
	
	Str = ""
	for i in range(M):
	for j in range(N):
		findWordsUtil(boggle, visited, i, j, Str)
boggle = [["G", "I", "Z"], ["U", "E", "K"], ["Q", "S", "E"]]


print("Following words of", "dictionary are present")
findWords(boggle)

// C# program to find words in dictionary from board of characters

using System;
using System.Collections.Generic;
class bn
{
	static readonly String []dictionary = { “HERO”, “JAVA”,
											“PYTHON”, "GUQ", "EE" };
	static readonly int n = dictionary.Length;
	static readonly int M = 3, N = 3;
	static bool isWord(String str)
	{
		for (int i = 0; i < n; i++)
			if (str.Equals(dictionary[i]))
				return true;
		return false;
	}
	static void findWordsUtil(char [,]boggle, bool [,]visited,
							int i, int j, String str)
	{
		visited[i, j] = true;
		str = str + boggle[i, j];
		if (isWord(str))
			Console.WriteLine(str);
		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 && !visited[row, col])
					findWordsUtil(boggle, visited, row, col, str);
		str = "" + str[str.Length - 1];
		visited[i, j] = false;
	}
	static void findWords(char [,]boggle)
	{
		bool [,]visited = new bool[M, N];
		String str = "";
		for (int i = 0; i < M; i++)
			for (int j = 0; j < N; j++)
				findWordsUtil(boggle, visited, i, j, str);
	}
	public static void Main(String []args)
	{
		char [,]boggle = { { ‘H’, ‘I’, ‘O’ },
						{ ‘A’, ‘E’, ‘R’ },
						{ ‘J’, ‘V’, ‘A’ } };


		Console.WriteLine("Following words of " +
						"dictionary are present");
		findWords(boggle);
	}
}

// JavaScript program to find words in dictionary from board of characters

<script>
	var dictionary = [“HERO”, “JAVA”, “PYTHON”, "GO"];
	var n = dictionary.length;
	var M = 3,
		N = 3;
	
	function isWord(str)
	{
	
				for (var i = 0; i < n; i++) if (str == dictionary[i]) return true;
		return false;
	}
	function findWordsUtil(boggle, visited, i, j, str)
	{
	
		visited[i][j] = true;
		str = str + boggle[i][j];
		if (isWord(str)) document.write(str + "<br>");
		for (var row = i - 1; row <= i + 1 && row < M; row++)
		for (var col = j - 1; col <= j + 1 && col < N; col++)
			if (row >= 0 && col >= 0 && !visited[row][col])
			findWordsUtil(boggle, visited, row, col, str);
		str = "" + str[str.length - 1];
		visited[i][j] = false;
	}
	function findWords(boggle)
	{
	
		var visited = Array.from(Array(M), () => new Array(N).fill(0));
		var str = "";
		for (var i = 0; i < M; i++)
		for (var j = 0; j < N; j++) findWordsUtil(boggle, visited, i, j, str);
	}
	var boggle = [
		["G", "I", "Z"],
		["U", "E", "K"],
		["Q", "S", "E"],
	];


	document.write("Following words of " + "dictionary are present <br>");
	findWords(boggle);
	
	</script>

Output: