Find all possible words in a board of characters

Question

This question has 2 possible solutions and I am trying to implement the DFS solution.

Here is the Trie and DFS solution: Boggle using Trie and DFS

Please review for performance.

Given a dictionary, a method to do lookup in 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 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 dictionary are present
         GEEKS
         QUIZ

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

namespace GraphsQuestions
{
    /// <summary>
    /// https://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/
    /// </summary>
    [TestClass]
    public class BoggleDfs
    {
        private List<string> _list = new List<string>();
        [TestMethod]
        public void GeeksForGeeksTest()
        {
            string[] dictionary = { "GEEKS", "FOR", "QUIZ", "GO" };
            char[,] boggle = {{'G', 'I', 'Z'},
                              {'U', 'E', 'K'},
                              {'Q', 'S', 'E'}};

            FindWords(boggle, dictionary);
            string[] expected = { "GEEKS", "QUIZ" };
            CollectionAssert.AreEqual(expected,_list.ToArray());
        }

        private void FindWords(char[,] boggle, string[] dictionary)
        {
            bool[,] visited = new bool[boggle.GetLength(0), boggle.GetLength(1)];
            StringBuilder str = new StringBuilder();
            //run DFS for all the options and compare with the dictionary
            for (int i = 0; i < boggle.GetLength(0); i++)
            {
                for (int j = 0; j < boggle.GetLength(1); j++)
                {
                    DFS(i, j, boggle, dictionary, str, visited);
                }
            }
        }

        private void DFS(int i, int j, char[,] boggle, string[] dictionary, StringBuilder str, bool[,] visited)
        {
            //mark we already visited this vertex
            visited[i, j] = true;

            str.Append(boggle[i, j]);
            if (IsWord(str.ToString(), dictionary))
            {
                _list.Add(str.ToString());
            }

            for (int row = i - 1; row <= i + 1 && row < boggle.GetLength(0); row++)
            {
                for (int col = j - 1; col <= j + 1 && col < boggle.GetLength(1); col++)
                {
                    if (col >= 0 && row >= 0 && !visited[row, col])
                    {
                        DFS(row, col, boggle, dictionary, str, visited);
                    }
                }
            }

            visited[i, j] = false;
            str.Remove(str.Length - 1, 1);
        }

        private bool IsWord(string str, string[] dictionary)
        {
            for (int i = 0; i < dictionary.Length; i++)
            {
                if (string.CompareOrdinal(str, dictionary[i]) == 0)
                {
                    return true;
                }
            }
            return false;
        }
    }
}

Answer 1

If I were you, I would stop having the tests mixed up with the implementation. It is somehow "smart", and for small projects like this, you can say it doesn't matter. But IMO it does matter because it prevents you from thinking properly about the design of you code.

Your implementation is a nearly one-to-one implementation of the C++ from Geeks and it appears rather C++-ish.

---

When it comes to naming, you should call your members after what they do or represent, - not after how they do it or is: DFS() as well as _list tell me nothing.

---

        for (int row = i - 1; row <= i + 1 && row < boggle.GetLength(0); row++)
        {
            for (int col = j - 1; col <= j + 1 && col < boggle.GetLength(1); col++)
            {
                if (col >= 0 && row >= 0 && !visited[row, col])
                {
                    DFS(row, col, boggle, dictionary, str, visited);
                }
            }
        }

IMO this way to determine the boundaries of the loops is hard to follow. The stop conditions are calculated in the for-statements while the start conditions are determined half in the for-statements and half in the if-statement.

A more clean and C#-ish way could be something like:

  int minRow = Math.Max(0, row - 1);
  int maxRow = Math.Min(rows, row + 2);
  int minCol = Math.Max(0, col - 1);
  int maxCol = Math.Min(cols, col + 2);

  for (int r = minRow; r < maxRow; r++)
  {
    for (int c = minCol; c < maxCol; c++)
    {
      if (!visited[r, c])
        Search(r, c);
    }
  }

The conditions are calculated once before the loops and hence separated nicely from the loops, and the loops are immediately easy to read and understand. For rows and cols see below.

---

    private bool IsWord(string str, string[] dictionary)
    {
        for (int i = 0; i < dictionary.Length; i++)
        {
            if (string.CompareOrdinal(str, dictionary[i]) == 0)
            {
                return true;
            }
        }
        return false;
    }

In C# this is a one-liner:

    private bool IsWord(string str, string[] dictionary)
    {
        return dictionary.Contains(str);
    }

---

        str.Remove(str.Length - 1, 1);

On the StringBuilder it is possible to set the length, which might be faster than removing a sequence of the one last character:

str.Length -= 1;

---

About the overall design:

On the one hand you let _list be a class member, while all other variables are arguments to the methods. I think I would make a statefull object having as many of the variables as possible as members:

  class WordFinder
  {
    private readonly char[,] boggle;
    private readonly bool[,] visited;
    private readonly int rows;
    private readonly int cols;
    private readonly List<string> words = new List<string>();
    private readonly StringBuilder word = new StringBuilder();
    private string[] dictionary;

    public WordFinder(char[,] boggle)
    {
      this.boggle = boggle;
      rows = boggle.GetLength(0);
      cols = boggle.GetLength(1);
      visited = new bool[rows, cols];
    }
    ...

Other than a reduced set of arguments for the methods one benefit is that the calculation of the boggle dimensions is done once here.

The FindWords method could then look like:

public IList<string> FindWords(string[] dictionary)
{
  this.dictionary = dictionary;
  words.Clear();
  word.Clear();

  for (int row = 0; row < rows; row++)
  {
    for (int col = 0; col < cols; col++)
    {
      Search(row, col);
    }
  }

  return words;
}

where the Search() method is:

private void Search(int row, int col)
{
  visited[row, col] = true;

  word.Append(boggle[row, col]);
  AddIfWord(word.ToString());

  int minRow = Math.Max(0, row - 1);
  int maxRow = Math.Min(rows, row + 2);
  int minCol = Math.Max(0, col - 1);
  int maxCol = Math.Min(cols, col + 2);

  for (int r = minRow; r < maxRow; r++)
  {
    for (int c = minCol; c < maxCol; c++)
    {
      if (!visited[r, c])
        Search(r, c);
    }
  }

  word.Length -= 1;
  visited[row, col] = false;
}

and AddIfWord() is

private void AddIfWord(string candidate)
{
  if (dictionary.Contains(candidate))
    words.Add(candidate);
}

Maybe word should be an argument rather than a member, because it is somehow a "local" variable, but on the other hand there is only one word at the time while the process is running, so it's fairly safe to let it be a member.

---

For convenience you could provide a static member as:

public static IList<string> FindWords(char[,] boggle, string[] dictionary)
{
  WordFinder finder = new WordFinder(boggle);
  return finder.FindWords(dictionary);
}

We could argue about if boggle and dictionary should be arguments to the constructor or FindWords() - that may be a matter of - if the process is about finding words from dictionary in boggle or visa versa and/or a matter of habit and taste.

---

When it comes to performance, there is not much to say, because the algorithm is "optimized" by its definition - I can't see any other ways to implement this implementation so to speak.

Answer 2

If you're deliberately not making dictionary a trie, then at least make it a set. This gives you O(1) lookup time rather than O(n).

However, instead of checking every possible combination against your dictionary, it's better to check each word separately. A method that only needs to find a single word can bail out early, which lets you skip a lot of work. It'll make your method O(n), based on dictionary size, rather than, uhh, O(scary), based on board dimensions. If we take into account that most languages only contain up to a few hundred thousand words, while a tiny 4x4 board already results in about 12 million possible words (compared to only 60 for a 2x2 board), it's clear that this scales much better.

With this optimization you can still find thousands of words on a 100x100 within a reasonable amount of time, while the original solution isn't really practical anymore beyond a 4x4 board. This actually gets you relatively close to the performance of your trie-based solution. The main difference is that a trie lets you skip some duplicate work by optimizing for words with a common prefix.