Boggle (Find all possible words in a board of characters) - GeeksforGeeks
http://www.geeksforgeeks.org/boggle-set-2-using-trie/
airbnb面试题汇总
boogle game直接找到所以单词可能出现的位置，然后dfs 感觉这样的代码比较短。。45min勉强敲的出来。。
这题面试来搞也太变态了，先用trie找出所有单词出现的路径map，然后dfs找出map里不重复的最大的。代码未验证~
我记得 就是找board中找不能重复位置的最大单词数量。。找单词的时候还定义了一个曼哈顿距离。。就是用来表示不能斜着走的 题目一共就是这3句话。。 另外board里面的字母都是大写
Read full article from Boggle (Find all possible words in a board of characters) - GeeksforGeeks
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 charactersNote that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.
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
The idea is to consider every character as a starting character and find all words starting with it. All words starting from a character can be found using Depth First Traversal. We do depth first traversal starting from every cell. We keep track of visited cells to make sure that a cell is considered only once in a word.
Note that the solution may print same word multiple times. For example, if we add “SEEK” to dictionary, it is printed multiple times. To avoid this, we can use hashing to keep track of all printed words.
// Let the given dictionary be followingstring dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};int n = sizeof(dictionary)/sizeof(dictionary[0]);// A given function to check if a given string is present in// dictionary. The implementation is naive for simplicity. As// per the question dictionary is givem to us.bool isWord(string &str){ // Linearly search all words for (int i=0; i<n; i++) if (str.compare(dictionary[i]) == 0) return true; return false;}// A recursive function to print all words present on bogglevoid findWordsUtil(char boggle[M][N], bool visited[M][N], int i, int j, string &str){ // Mark current cell as visited and append current character // to str visited[i][j] = true; str = str + boggle[i][j]; // If str is present in dictionary, then print it if (isWord(str)) cout << str << endl; // Traverse 8 adjacent cells of boggle[i][j] for (int row=i-1; row<=i+1 && row<M; row++) for (int col=j-1; col<=j+1 && col<N; col++) if (row>=0 && col>=0 && !visited[row][col]) findWordsUtil(boggle,visited, row, col, str); // Erase current character from string and mark visited // of current cell as false str.erase(str.length()-1); visited[i][j] = false;}// Prints all words present in dictionary.void findWords(char boggle[M][N]){ // Mark all characters as not visited bool visited[M][N] = {{false}}; // Initialize current string string str = ""; // Consider every character and look for all words // starting with this character for (int i=0; i<M; i++) for (int j=0; j<N; j++) findWordsUtil(boggle, visited, i, j, str);}http://www.geeksforgeeks.org/boggle-set-2-using-trie/
void insert(TrieNode *root, char *Key){ int n = strlen(Key); TrieNode * pChild = root; for (int i=0; i<n; i++) { int index = char_int(Key[i]); if (pChild->Child[index] == NULL) pChild->Child[index] = getNode(); pChild = pChild->Child[index]; } // make last node as leaf node pChild->leaf = true;}// function to check that current location// (i and j) is in matrix rangebool isSafe(int i, int j, bool visited[M][N]){ return (i >=0 && i < M && j >=0 && j < N && !visited[i][j]);}// A recursive function to print all words present on bogglevoid searchWord(TrieNode *root, char boggle[M][N], int i, int j, bool visited[][N], string str){ // if we found word in trie / dictionary if (root->leaf == true) cout << str << endl ; // If both I and j in range and we visited // that element of matrix first time if (isSafe(i, j, visited)) { // make it visited visited[i][j] = true; // traverse all childs of current root for (int K =0; K < SIZE; K++) { if (root->Child[K] != NULL) { // current character char ch = (char)K + (char)'A' ; // Recursively search reaming character of word // in trie for all 8 adjacent cells of boggle[i][j] if (isSafe(i+1,j+1,visited) && boggle[i+1][j+1] == ch) searchWord(root->Child[K],boggle,i+1,j+1,visited,str+ch); if (isSafe(i, j+1,visited) && boggle[i][j+1] == ch) searchWord(root->Child[K],boggle,i, j+1,visited,str+ch); if (isSafe(i-1,j+1,visited) && boggle[i-1][j+1] == ch) searchWord(root->Child[K],boggle,i-1, j+1,visited,str+ch); if (isSafe(i+1,j, visited) && boggle[i+1][j] == ch) searchWord(root->Child[K],boggle,i+1, j,visited,str+ch); if (isSafe(i+1,j-1,visited) && boggle[i+1][j-1] == ch) searchWord(root->Child[K],boggle,i+1, j-1,visited,str+ch); if (isSafe(i, j-1,visited)&& boggle[i][j-1] == ch) searchWord(root->Child[K],boggle,i,j-1,visited,str+ch); if (isSafe(i-1,j-1,visited) && boggle[i-1][j-1] == ch) searchWord(root->Child[K],boggle,i-1, j-1,visited,str+ch); if (isSafe(i-1, j,visited) && boggle[i-1][j] == ch) searchWord(root->Child[K],boggle,i-1, j, visited,str+ch); } } // make current element unvisited visited[i][j] = false; }}// Prints all words present in dictionary.void findWords(char boggle[M][N], TrieNode *root){ // Mark all characters as not visited bool visited[M][N]; memset(visited,false,sizeof(visited)); TrieNode *pChild = root ; string str = ""; // traverse all matrix elements for (int i = 0 ; i < M; i++) { for (int j = 0 ; j < N ; j++) { // we start searching for word in dictionary // if we found a character which is child // of Trie root if (pChild->Child[char_int(boggle[i][j])] ) { str = str+boggle[i][j]; searchWord(pChild->Child[char_int(boggle[i][j])], boggle, i, j, visited, str); str = ""; } } }}airbnb面试题汇总
boogle game直接找到所以单词可能出现的位置，然后dfs 感觉这样的代码比较短。。45min勉强敲的出来。。
这题面试来搞也太变态了，先用trie找出所有单词出现的路径map，然后dfs找出map里不重复的最大的。代码未验证~
我记得 就是找board中找不能重复位置的最大单词数量。。找单词的时候还定义了一个曼哈顿距离。。就是用来表示不能斜着走的 题目一共就是这3句话。。 另外board里面的字母都是大写
Read full article from Boggle (Find all possible words in a board of characters) - GeeksforGeeks
