Coderust: Hacking the Coding Interview/

...

/

Boggle

Boggle

Build a game known as Boggle, find the words of a dictionary from a grid of characters in this game.

We'll cover the following...

Statement

Given an n×nn \times n grid of characters and a dictionary, find all the words that 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 direction: up, down, left, right, or along any diagonal.

  • We can use the character at each position in the grid only once while making a word.

Example

Suppose we have a 3×33 \times 3 grid and a dictionary as input. We can make six words from the grid that are present in the dictionary. The green highlighted characters indicate that they form the word eateat in the grid, which is also present in the dictionary.

In the grid, we start at character EE, then move up and left (along a diagonal) for AA, and then right to TT to make eateat.

g d Dictionary cat cater art toon moon not eat ton Output Words not cat art cater ton eat q C A T R R E T O N

Sample input

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

dictionary = {"cat", "cater", "cartoon", "toon", "moon", "not", "tone", "apple", "ton", "art"}

Expected output

output = ["art", "tone", "cat", "cater", "not", "ton"]

Try it yourself

#include <string>
#include <list>
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
class Boggle {
 public:
	// Code assumes that both dimensions of the grid are the same
	vector<vector<char>> grid;
	unordered_set<string> dictionary;
	vector<vector<bool>> state;
	Boggle(const vector<vector<char>>& g, const unordered_set<string>& d)
			: grid(g), dictionary(d) {
		// TODO: Write - Your - Code
	}
	// Challenge function
	unordered_set<string> FindAllWords() {
		// TODO: Write - Your - Code
		unordered_set<string> words;
		return words;
	}
};

Solution

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 ...