word search Algorithm
A word search, word find, word seek, word sleuth or mystery word puzzle is a word game that consists of the letters of words put in a grid, which normally has a rectangular or square shape. Also in common with these latter puzzles, have had complete books and mobile applications dedicated to them. was originally designed and published by Norman E. Gibat in the Selenby digest on March 1, 1968, in Norman, Oklahoma, although the Spanish puzzle creator Pedro Ocón de Oro was printing" Sopas de letras" (Spanish" Soup of letter") before that date. Other digital and tabletop word search games include A manner with word, Boggle, Bookworm, Letterpress, Outworded, Puzzlage, Ruzzle, Wonderword, Wordament, WordSpot, word Streak with Friends, and word Winder. One teacher send them around the state to various friends in other schools.
/*
* Given a 2D board and list of words from a dictionary,
* find all the possible words on board fromt the list.
* Example:
* words = ["oath","pea","eat","rain"]
* board =
* [
* ['o','a','a','n'],
* ['e','t','a','e'],
* ['i','h','k','r'],
* ['i','f','l','v']
* ]
*
* Output: ["eat", "oath"]
*
* Source : LeetCode Problem 212
*
* Approach:
*
* We can use backtracking(dfs) to traverse from each character on board
* to all four direction. In order to do a fast searching, we can use
* a trie from words in dictionary, as soon as we find a word from dictionary
* in trie, we remove it from trie, so we don't have duplicates.
* Also, we can use the board to mark '#' as visited character to
* achieve backtracking.
*/
#include <vector>
#include <iostream>
struct TrieNode {
std::string word;
std::vector<TrieNode*> children;
TrieNode():
word{""}, children{std::vector<TrieNode*>(26, nullptr)}{}
};
TrieNode* build_trie(const std::vector<std::string>& dictionary)
{
TrieNode* root = new TrieNode();
for (auto word: dictionary) {
TrieNode* curr = root;
for (auto c: word) {
int index = c - 'a';
if (curr->children[index] == nullptr) {
curr->children[index] = new TrieNode();
}
curr = curr->children[index];
}
curr->word = word;
}
return root;
}
void backtrack(std::vector<std::vector<char>>& board,
TrieNode* root, int i, int j, std::vector<std::string>& result)
{
char c = board[i][j];
if (c == '#' || root == nullptr) {
return;
}
int index = c - 'a';
TrieNode* curr = root->children[index];
if (curr == nullptr) {
return;
}
if (curr->word != "") {
result.push_back(curr->word);
// Reset to avoid duplicates.
curr->word = "";
}
board[i][j] = '#';
if (i > 0) {
backtrack(board, curr, i - 1, j, result);
}
if (j > 0) {
backtrack(board, curr, i, j - 1, result);
}
if (i < board.size() - 1) {
backtrack(board, curr, i + 1, j, result);
}
if (j < board[0].size() - 1) {
backtrack(board, curr, i, j + 1, result);
}
board[i][j] = c;
}
std::vector<std::string> find_words(std::vector<std::vector<char>>& board,
std::vector<std::string>& dictionary)
{
std::vector<std::string> result;
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
TrieNode* root = build_trie(dictionary);
backtrack(board, root, i, j, result);
}
}
return result;
}
template <typename T>
void print_vector(const std::vector<T>& vec)
{
std::cout << "{ ";
for (auto t : vec) {
std::cout << t << " ";
}
std::cout << " }" << std::endl;
}
void print_board(const std::vector<std::vector<char>>& board)
{
for (auto v: board) {
print_vector(v);
}
}
int main()
{
std::vector<std::vector<char>> board = {
{'o','a','a','n'},
{'e','t','a','e'},
{'i','h','k','r'},
{'i','f','l','v'}
};
std::vector<std::string> dictionary = {
"oath","pea","eat","rain"
};
std::vector<std::string> result = find_words(board, dictionary);
std::cout << "Board:" << std::endl;
print_board(board);
std::cout << "Dictionary:" << std::endl;
print_vector(dictionary);
std::cout << "Result:" << std::endl;
print_vector(result);
return 0;
}
