给定一个字典，一个在字典中查找的方法，以及一个每个单元格都有一个字符的mxn板。找出所有可能由一系列相邻字符组成的单词。请注意，我们可以移动到8个相邻字符中的任意一个，但一个单词不应该有同一单元格的多个实例。 例子：
null
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
我们强烈建议您在继续解决方案之前单击此处并进行练习。
这个想法是考虑每个字符作为一个起始字符，并找到所有单词从它开始。所有以字符开头的单词都可以使用 深度优先遍历 .我们从每个单元开始进行深度优先遍历。我们跟踪访问过的单元格，以确保一个单元格在一个单词中只被视为一次。
C++
// C++ program for Boggle game #include <cstring> #include <iostream> using namespace std; #define M 3 #define N 3 // Let the given dictionary be following string 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 given 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 boggle void 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); } // Driver program to test above function int main() { char boggle[M][N] = { { 'G' , 'I' , 'Z' }, { 'U' , 'E' , 'K' }, { 'Q' , 'S' , 'E' } }; cout << "Following words of dictionary are present" ; findWords(boggle); return 0; } |
JAVA
// Java program for Boggle game class GFG { // Let the given dictionary be following static final String dictionary[] = { "GEEKS" , "FOR" , "QUIZ" , "GUQ" , "EE" }; static final int n = dictionary.length; static final int M = 3 , N = 3 ; // 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 given to us. static boolean isWord(String str) { // Linearly search all words for ( int i = 0 ; i < n; i++) if (str.equals(dictionary[i])) return true ; return false ; } // A recursive function to print all words present on boggle static void findWordsUtil( char boggle[][], boolean visited[][], 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)) System.out.println(str); // 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 = "" + str.charAt(str.length() - 1 ); visited[i][j] = false ; } // Prints all words present in dictionary. static void findWords( char boggle[][]) { // Mark all characters as not visited boolean visited[][] = new boolean [M][N]; // 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); } // Driver program to test above function public static void main(String args[]) { char boggle[][] = { { 'G' , 'I' , 'Z' }, { 'U' , 'E' , 'K' }, { 'Q' , 'S' , 'E' } }; System.out.println( "Following words of dictionary are present" ); findWords(boggle); } } |
Python3
# Python3 program for Boggle game # Let the given dictionary be following dictionary = [ "GEEKS" , "FOR" , "QUIZ" , "GO" ] n = len (dictionary) M = 3 N = 3 # 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 given to us. def isWord( Str ): # Linearly search all words for i in range (n): if ( Str = = dictionary[i]): return True return False # A recursive function to print all words present on boggle def findWordsUtil(boggle, visited, i, j, 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 )): print ( Str ) # Traverse 8 adjacent cells of boggle[i,j] row = i - 1 while row < = i + 1 and row < M: col = j - 1 while col < = j + 1 and col < N: if (row > = 0 and col > = 0 and not visited[row][col]): findWordsUtil(boggle, visited, row, col, Str ) col + = 1 row + = 1 # Erase current character from string and # mark visited of current cell as false Str = "" + Str [ - 1 ] visited[i][j] = False # Prints all words present in dictionary. def findWords(boggle): # Mark all characters as not visited visited = [[ False for i in range (N)] for j in range (M)] # Initialize current string Str = "" # Consider every character and look for all words # starting with this character for i in range (M): for j in range (N): findWordsUtil(boggle, visited, i, j, Str ) # Driver Code boggle = [[ "G" , "I" , "Z" ], [ "U" , "E" , "K" ], [ "Q" , "S" , "E" ]] print ( "Following words of" , "dictionary are present" ) findWords(boggle) # This code is contributed by divyesh072019. |
C#
// C# program for Boggle game using System; using System.Collections.Generic; class GFG { // Let the given dictionary be following static readonly String []dictionary = { "GEEKS" , "FOR" , "QUIZ" , "GUQ" , "EE" }; static readonly int n = dictionary.Length; static readonly int M = 3, N = 3; // 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 given to us. static bool isWord(String str) { // Linearly search all words for ( int i = 0; i < n; i++) if (str.Equals(dictionary[i])) return true ; return false ; } // A recursive function to print all words present on boggle static void findWordsUtil( char [,]boggle, bool [,]visited, 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)) Console.WriteLine(str); // 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 = "" + str[str.Length - 1]; visited[i, j] = false ; } // Prints all words present in dictionary. static void findWords( char [,]boggle) { // Mark all characters as not visited bool [,]visited = new bool [M, N]; // 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); } // Driver Code public static void Main(String []args) { char [,]boggle = { { 'G' , 'I' , 'Z' }, { 'U' , 'E' , 'K' }, { 'Q' , 'S' , 'E' } }; Console.WriteLine( "Following words of " + "dictionary are present" ); findWords(boggle); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program for Boggle game // Let the given dictionary be following var dictionary = [ "GEEKS" , "FOR" , "QUIZ" , "GO" ]; var n = dictionary.length; var M = 3, N = 3; // 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 given to us. function isWord(str) { // Linearly search all words for ( var i = 0; i < n; i++) if (str == dictionary[i]) return true ; return false ; } // A recursive function to print all words present on boggle function findWordsUtil(boggle, visited, i, j, 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)) document.write(str + "<br>" ); // Traverse 8 adjacent cells of boggle[i,j] for ( var row = i - 1; row <= i + 1 && row < M; row++) for ( var 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 = "" + str[str.length - 1]; visited[i][j] = false ; } // Prints all words present in dictionary. function findWords(boggle) { // Mark all characters as not visited var visited = Array.from(Array(M), () => new Array(N).fill(0)); // Initialize current string var str = "" ; // Consider every character and look for all words // starting with this character for ( var i = 0; i < M; i++) for ( var j = 0; j < N; j++) findWordsUtil(boggle, visited, i, j, str); } // Driver Code var boggle = [ [ "G" , "I" , "Z" ], [ "U" , "E" , "K" ], [ "Q" , "S" , "E" ], ]; document.write( "Following words of " + "dictionary are present <br>" ); findWords(boggle); // This code is contributed by rdtank. </script> |
输出
Following words of dictionary are presentGEEKSQUIZ
请注意，上述解决方案可能会多次打印同一个单词。例如，如果我们在字典中添加“SEEK”，它会被打印多次。为了避免这种情况，我们可以使用哈希来跟踪所有打印的单词。 在下面的第2组中，我们讨论了基于Trie的优化解决方案： Boggle |集合2（使用Trie） 本文由 里沙布 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
