1
\$\begingroup\$

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>();
    }
}
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – dfhwze Jun 30 at 17:08
  • 1
    \$\begingroup\$ 2 spaces does stimulate the use of nested 'for if do while do do if '.. blocks :-p \$\endgroup\$ – dfhwze Jun 30 at 17:16
  • 2
    \$\begingroup\$ As always amazing review. I wasn't sure about the return value I guess you are right. \$\endgroup\$ – Gilad Jun 30 at 17:17
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – dfhwze Jun 30 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.