Boggle

editor-page-cover

Problem Statement

Given a N×N grid of characters and a dictionary, find all words which can be made from the characters in the grid and are present in the given dictionary.

A word can start and end at any character in the grid. The next character must be adjacent to the previous character in any of the directions: up, down, left, right and diagonal.

The character at each position in the grid can be used only once while making a word.

Suppose we have a 3×3 grid and a dictionary as input. Six words can be made from the grid which are present in the dictionary. Green highlighted characters indicate that they form the word EAT in the grid which is also present in the dictionary.

In the grid, we start at character E, then move to upper diagonal for A and then right to T to make EAT.

widget

Hint

  • Backtracking

Try it yourself

Your code will be tested for the grid:

grid = [['c', 'a', 't'],
        ['r', 'r', 'e'],
        ['t', 'o', 'n']]

and the dictionary:

dictionary = {"cat", "cater", "cartoon", "toon", "moon", "not", "tone", "apple", "ton", "art"}
class Boggle {
  public:
    Boggle(const vector<vector<char>>& grid, const unordered_set<string>& dictionary){
      //TODO: Write - Your - Code
    }

    unordered_set<string> find_all_words(){
      //TODO: Write - your - Code
      unordered_set<string> words; 
      return words;
    }
};

Solution

class Boggle {
  // code assumes that both dimensions of grid are same
  public:
    vector<vector<char>> grid;
    unordered_set<string> dictionary;
    vector<vector<bool>> state;

    list<pair<int, int>> find_all_nbrs(int x, int y) {
      list<pair<int, int>> nbrs;
      int start_x = std::max(0, x - 1);
      int start_y = std::max(0, y - 1);
      int end_x = std::min((int)(grid.size() - 1), x + 1);
      int end_y = std::min((int)(grid.size() - 1), y + 1);
      for (int i = start_x; i <= end_x; ++i) {
        for (int j = start_y; j <= end_y; ++j) {
          if (state[i][j]) {
            continue;
          }
          nbrs.push_back(pair<int, int>(i, j));
        }
      }
      return nbrs;
    }

    void find_words_rec(int i, int j,string& current,unordered_set<string>& words) {
      
      if (!current.empty() && dictionary.find(current) != dictionary.end()) {
        words.insert(current);
      }
      // we can really speed up our algorithm if we have prefix method available
      // for our dictionary by using code like below
      /*
      if (!dictionary.is_prefix(current)) {
        // if current word is not prefix of any word in dictionary
        // we don't need to continue with search
        return;
      }
      */
      list<pair<int, int>> nbrs = find_all_nbrs(i, j);
      for (auto& pr : nbrs) {      
        current += grid[pr.first][pr.second];
        state[pr.first][pr.second] = true;
        find_words_rec(pr.first, pr.second, current, words);
        current.resize(current.size() - 1);
        state[pr.first][pr.second] = false;
      }
    }

    Boggle(const vector<vector<char>>& g, const unordered_set<string>& d) : grid(g), dictionary(d) { 
      state.resize(g.size());
      for (vector<bool>& v : state) {
        v.resize(g.back().size());
      }
    }

    unordered_set<string> find_all_words(){
      unordered_set<string> words;
      string current_word;
      for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid.size(); ++j) {
          find_words_rec(i, j, current_word, words);
        }
      }
      return words;
    }
};

int main(){
  vector<vector<char>> grid = {{'c', 'a', 't'},
                               {'r', 'r', 'e'},
                               {'t', 'o', 'n'}};
  
  unordered_set<string> dictionary = {"cat", "cater", "cartoon", "art", "toon", "moon", "eat", "ton"};
  Boggle b(grid, dictionary);
  unordered_set<string> words = b.find_all_words();
  for (auto& s: words) {
    cout << s << endl;
  }
  return 0;
}

Solution Explanation

Runtime complexity

The runtime complexity of this solution is exponential, O(NN)O(N^{N}), where N is the dimension of the grid.

Memory complexity

The memory complexity of this solution is quadratic, O(N2)O(N^{2}), where N is the dimension of the grid.


Solution Breakdown

This is a backtracking problem. We start with one character in the grid and try to make as many words as possible starting with that character. We repeat the same process for all characters in the grid.

To find all the words starting with a character, we use an algorithm very similar to depth-first search. As every character from the grid can appear only once in a word, we’ll need to maintain a boolean matrix to indicate if the corresponding character in the grid is used to make this word.

We can really speed up our algorithm if we have a prefix method available for our dictionary.

Let’s consider an example below where we want to find all words starting with character EE (in 2nd2^{nd} row and 3rd3^{rd} column of the example grid above).

For this example we’ll assume that the dictionary has a prefix() method which returns true if a string is a prefix of a valid word.

  • We’ll start with EE. From our dictionary we know that EE is a prefix of a word, so we’ll keep EE and continue after marking EE as used in the boolean matrix.

  • EE has 55 unused neighbors, i.e., AA, TT, RR, OO, NN. First we’ll proceed with first neighbor i.e. AA. EAEA is a valid prefix.

  • AA has 4 unused neighbors i.e. CC, TT, RR, RR. EE is a neighbor of AA, but we’ll not consider it as it is already used. First, we’ll try CC but EACEAC is neither a valid word nor a prefix to valid words in our dictionary. So, we’ll move to the next neighbor, TT and EATEAT is a valid word.

  • We’ll add EATEAT to the output words list and then continue to neighbors of TT. But no neighbor of TT can be part of a prefix or a valid word, so we’ll backtrack and continue with remaining neighbors of AA from the previous step.

  • In this case, they are RR, RR and EAREAR, EAREAR is neither a valid word nor prefix a to a valid word in the dictionary, so we’ll backtrack.

  • While backtracking we always reset used flags so that this character can be used in some other path. We’ll backtrack once again and will look at other neighbors of EE, i.e., TT, RR, OO, NN. We’ll continue until all paths starting from EE are explored.