Boggle using Trie and DFS

Question

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

Please review for performance and any other comments, thanks.

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++)
 {
 //all the words start with one of the letters in the head of the Trie
 if (root.Head.Edges.ContainsKey(boggle[i, 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()
 {
 Head = new TrieNode();
 }
 /** Inserts a word into the trie. */
 public void Insert(string word)
 {
 var current = Head;
 for (int i = 0; i < word.Length; i++)
 {
 if (!current.Edges.ContainsKey(word[i]))
 {
 current.Edges.Add(word[i], new TrieNode());
 }
 current = current.Edges[word[i]];
 }
 current.IsTerminal = true;
 }
 /** Returns if the word is in the trie. */
 public bool Search(string word)
 {
 var current = Head;
 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)
 {
 var current = Head;
 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>();
 }
}

Answer 1

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.

• dfhwze: 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: 2 spaces does stimulate the use of nested 'for if do while do do if '.. blocks :-p
• Gilad: As always amazing review. I wasn't sure about the return value I guess you are right.
• dfhwze: 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