Dado un diccionario, un método para realizar búsquedas en el diccionario y un tablero M x N donde cada celda tiene un carácter. Encuentra todas las palabras posibles que pueden estar formadas por una secuencia de caracteres adyacentes. Tenga en cuenta que podemos movernos a cualquiera de los 8 caracteres adyacentes, pero una palabra no debe tener varias instancias de la misma celda.
Ejemplo:
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
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
La idea es considerar cada carácter como un carácter inicial y encontrar todas las palabras que comiencen con él. Todas las palabras que comienzan con un carácter se pueden encontrar utilizando Depth First Traversal . Hacemos un recorrido primero en profundidad a partir de cada celda. Realizamos un seguimiento de las celdas visitadas para asegurarnos de que una celda se considere solo una vez en una palabra.
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\n";
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>
Producción
Following words of dictionary are present GEEKS QUIZ
Tenga en cuenta que la solución anterior puede imprimir la misma palabra varias veces. Por ejemplo, si agregamos «BUSCAR» al diccionario, se imprime varias veces. Para evitar esto, podemos usar hashing para realizar un seguimiento de todas las palabras impresas.
Para mejorar la complejidad del tiempo, podemos usar unordered_set (en C++) o un diccionario (en Python), que requiere un tiempo de búsqueda constante. Ahora la complejidad del tiempo, ya que estamos haciendo un recorrido primero en profundidad para cada posición en la array, por lo que n*m(tiempo para un DFS) = n*m( |V| + |E|) donde |V| es el número total de Nodes y |E| es el número total de aristas que son iguales a n*m. Asi que,
Complejidad de Tiempo: O(N 2 *M 2 )
Espacio Auxiliar: O(N*M)
En el conjunto 2 a continuación, hemos discutido la solución optimizada basada en Trie:
Boggle | Conjunto 2 (Usando Trie)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA