# Boggle using Trie and DFS

I already mentioned in my previous code review, there are two solutions for this problem https://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/

this is the first: Find all possible words in a board of characters

and here comes the second.

Original question is:

Given a dictionary, a method to do a lookup in the dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of the same cell.

Example:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
boggle[][]   = {{'G','I','Z'},
{'U','E','K'},
{'Q','S','E'}};
isWord(str): returns true if str is present in dictionary
else false.

Output:  Following words of the dictionary are present
GEEKS
QUIZ


using System;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TrieQuestions
{
[TestClass]
public class BoggleTrie
{
[TestMethod]
public void BoggleTrieTest()
{
string[] dictionary = { "GEEKS", "FOR", "QUIZ", "GEE" };
char[,] boggle = {{'G','I','Z'},
{'U','E','K'},
{'Q','S','E'}
};

Trie tree = new Trie();
foreach (var word in dictionary)
{
tree.Insert(word);
}

FindWords(boggle, tree);
}

private void FindWords(char[,] boggle, Trie root)
{
int M = boggle.GetLength(0);
int N = boggle.GetLength(1);
bool[,] visited = new bool[M,N];
StringBuilder str = new StringBuilder();

for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
{
str.Append(boggle[i, j]);
SearchWord(root.Head.Edges[boggle[i,j]], boggle, i, j, visited, str);
}
str.Clear();
}
}
}

private void SearchWord(TrieNode child, char[,] boggle, int i, int j, bool[,] visited, StringBuilder str)
{
if (child.IsTerminal)
{
Console.WriteLine(str.ToString());
}

int M = boggle.GetLength(0);
int N = boggle.GetLength(1);

if (IsSafe(M, N, i, j, visited))
{
visited[i, j] = true;

foreach (var edge in child.Edges)
{
for (int row = i - 1; row <= i + 1; row++)
{
for (int col = j - 1; col <= j + 1; col++)
{
if (IsSafe(M, N, row, col, visited) && boggle[row,col] == edge.Key)
{
SearchWord(edge.Value, boggle, row, col, visited, str.Append(edge.Key));
}
}
}

}

visited[i, j] = false;
}
}

private bool IsSafe(int M, int N, int i, int j, bool[,] visited)
{
return i < M && i >= 0 && j < N && j >= 0 && !visited[i, j];
}
}
}


NO NEED TO REVIEW THE TRIE code

here only for reference

public class Trie
{
public TrieNode Head { get; set; }

/** Initialize your data structure here. */
public Trie()
{
}

/** Inserts a word into the trie. */
public void Insert(string word)
{
for (int i = 0; i < word.Length; i++)
{
if (!current.Edges.ContainsKey(word[i]))
{
}
current = current.Edges[word[i]];
}
current.IsTerminal = true;
}

/** Returns if the word is in the trie. */
public bool Search(string word)
{
for (int i = 0; i < word.Length; i++)
{
if (!current.Edges.ContainsKey(word[i]))
{
return false;
}
current = current.Edges[word[i]];
}
return current.IsTerminal == true;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public bool StartsWith(string prefix)
{
for (int i = 0; i < prefix.Length; i++)
{
if (!current.Edges.ContainsKey(prefix[i]))
{
return false;
}
current = current.Edges[prefix[i]];
}
return true;
}
}

public class TrieNode
{
public Dictionary<char, TrieNode> Edges { get; set; }
public bool IsTerminal { get; set; }
public TrieNode()
{
Edges = new Dictionary<char, TrieNode>();
}
}


When testing you solution with the following dictionary:

      string[] dictionary = { "GEEKS", "GEEKSQ", "SEEK", "EGIZK", "EEK", "FOR", "QUIZ", "GO" };


I get this result:

GEEKS
GEEKSQ
EGIZK
EGIZKEK
QUIZ
SEEK
SEEKEEK
EEK


The reason must be that you don't reset the str object after each recursive call to SearchWord:

if (IsSafe(M, N, row, col, visited) && boggle[row,col] == edge.Key)
{
SearchWord(edge.Value, boggle, row, col, visited, str.Append(edge.Key));
}


You must remove the previous char before the next boggle[row, col] is tested in the recursive call.

   if (IsSafe(M, N, row, col, visited) && boggle[row,col] == edge.Key)
{
SearchWord(edge.Value, boggle, row, col, visited, str.Append(edge.Key));
str.Length--;
}


  if (IsSafe(M, N, i, j, visited))
{
visited[i, j] = true;


I see no reason for this check, because you know that it's safe from the previous recursion:

if (IsSafe(M, N, row, col, visited) && boggle[row,col] == edge.Key)
{
SearchWord(edge.Value, boggle, row, col, visited, str.Append(edge.Key));


    if (IsSafe(M, N, i, j, visited))
{
visited[i, j] = true;

foreach (var edge in child.Edges)
{
for (int row = i - 1; row <= i + 1; row++)
{
for (int col = j - 1; col <= j + 1; col++)
{
if (IsSafe(M, N, row, col, visited) && boggle[row,col] == edge.Key)
{
SearchWord(edge.Value, boggle, row, col, visited, str.Append(edge.Key));
}
}
}

}

visited[i, j] = false;
}


I think there is a possibility for optimization here: Instead of iterating all the edges on the current node it is only necessary to test those where boggle[row, col] is safe:

  // if (IsSafe(M, N, i, j, visited))
{
visited[i, j] = true;

//foreach (var edge in child.Edges)
{
for (int row = i - 1; row <= i + 1; row++)
{
for (int col = j - 1; col <= j + 1; col++)
{
if (IsSafe(M, N, row, col, visited))
{
char key = boggle[row, col];
if (child.Edges.TryGetValue(key, out TrieNode edge))
{
SearchWord(edge, boggle, row, col, visited, str.Append(key));
str.Length--;
}
}
}

}
}

visited[i, j] = false;
}


So a gentle rewriting of SearchWord - eliminating the need for IsSafe() could be:

private void SearchWord(TrieNode child, char[,] boggle, int i, int j, bool[,] visited, StringBuilder str)
{
if (child.IsTerminal)
{
Console.WriteLine(str.ToString());
}

int M = boggle.GetLength(0);
int N = boggle.GetLength(1);

int minRow = Math.Max(0, i - 1);
int maxRow = Math.Min(M, i + 2);
int minCol = Math.Max(0, j - 1);
int maxCol = Math.Min(N, j + 2);

visited[i, j] = true;

for (int row = minRow; row < maxRow; row++)
{
for (int col = minCol; col < maxCol; col++)
{
if (visited[row, col])
continue;

char key = boggle[row, col];
if (child.Edges.TryGetValue(key, out TrieNode edge))
{
SearchWord(edge, boggle, row, col, visited, str.Append(key));
str.Length--;
}
}
}

visited[i, j] = false;
}


Besides that I have the usual "complaints" about naming, mixing test and implementation, not repeating yourself, the benefits of creating a proper class as with the other version - and it's of course sloppy just to write the result to the console, instead of returning it.

In order to make it more C#-style you could rewrite it, so the api looks like:

public IEnumerable<string> FindWords(char[,] boggle, Trie root)


and:

private IEnumerable<string> SearchWord(TrieNode child, char[,] boggle, int i, int j, bool[,] visited, StringBuilder str)


and then use yield return str.ToString() when ever a word is found.

• I noticed you use indentations of 2 spaces. The default is 4 on CR, if I'm not mistaken. You find this to have improved readability? – dfhwze Jun 30 '19 at 17:08
• 2 spaces does stimulate the use of nested 'for if do while do do if '.. blocks :-p – dfhwze Jun 30 '19 at 17:16
• As always amazing review. I wasn't sure about the return value I guess you are right. – Gilad Jun 30 '19 at 17:17
• It does add readability for such cases. The question is whether such cases should be rewritten in their entirety :) But this is out of scope of this OP/Answer. I will stop polluting your comments :p – dfhwze Jun 30 '19 at 17:27