Dada una serie de strings str[] y una string key , la tarea es comprobar si la ortografía de la clave es correcta o no. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, imprima la ortografía correcta sugerida.
Ejemplos:
Entrada: str[] = { “gee”, “geeks”, “ape”, “apple”, “geeksforgeeks” }, key = “geek”
Salida: geeks geeksforgeeks
Explicación:
La string “geek” no está presente en la array de instrumentos de cuerda.
Por lo tanto, las palabras sugeridas son { “geeks”, “geeksforgeeks” }.Entrada: str[] = { “gee”, “geeks”, “ape”, “apple”, “arp” }, key = “geeks”
Salida: SÍ.
Enfoque: El problema se puede resolver usando Trie . La idea es atravesar la array de string, str[] e insertar la string en el Trie de modo que cada Node del Trie contenga el carácter de la string y un valor booleano para verificar si el carácter es el último carácter de la string o no. Siga los pasos a continuación para resolver el problema:
- Inicialice un Trie , digamos root , de modo que cada Node del Trie consista en un carácter de una string y un valor booleano para verificar si el carácter es el último carácter de la string o no.
- Atraviese la array de strings arr[] e inserte todas las strings en el Trie .
- Por último, atraviesa la tecla de string . Para cada i -ésimo carácter, compruebe si el carácter está presente en el Trie o no. Si se determina que es cierto, pase al siguiente Node del Trie.
- De lo contrario, imprima todas las strings posibles cuyo prefijo sea la clave de string .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a Trie node
struct TrieNode {
// Store address of a character
TrieNode* Trie[256];
// Check if the character is
// last character of a string or not
bool isEnd;
// Constructor function
TrieNode()
{
for (int i = 0; i < 256; i++) {
Trie[i] = NULL;
}
isEnd = false;
}
};
// Function to insert a string into Trie
void InsertTrie(TrieNode* root, string s)
{
TrieNode* temp = root;
// Traverse the string, s
for (int i = 0; i < s.length(); i++) {
if (temp->Trie[s[i]] == NULL) {
// Initialize a node
temp->Trie[s[i]] = new TrieNode();
}
// Update temp
temp = temp->Trie[s[i]];
}
// Mark the last character of
// the string to true
temp->isEnd = true;
}
// Function to print suggestions of the string
void printSuggestions(TrieNode* root, string res)
{
// If current character is
// the last character of a string
if (root->isEnd == true) {
cout << res << " ";
}
// Iterate over all possible
// characters of the string
for (int i = 0; i < 256; i++) {
// If current character
// present in the Trie
if (root->Trie[i] != NULL) {
// Insert current character
// into Trie
res.push_back(i);
printSuggestions(root->Trie[i], res);
res.pop_back();
}
}
}
// Function to check if the string
// is present in Trie or not
bool checkPresent(TrieNode* root, string key)
{
// Traverse the string
for (int i = 0; i < key.length(); i++) {
// If current character not
// present in the Trie
if (root->Trie[key[i]] == NULL) {
printSuggestions(root, key.substr(0, i));
return false;
}
// Update root
root = root->Trie[key[i]];
}
if (root->isEnd == true) {
return true;
}
printSuggestions(root, key);
return false;
}
// Driver Code
int main()
{
// Given array of strings
vector<string> str = { "gee", "geeks", "ape",
"apple", "geeksforgeeks" };
string key = "geek";
// Initialize a Trie
TrieNode* root = new TrieNode();
// Insert strings to trie
for (int i = 0; i < str.size(); i++) {
InsertTrie(root, str[i]);
}
if (checkPresent(root, key)) {
cout << "YES";
}
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
// Structure of a Trie node
class TrieNode
{
// Store address of a character
TrieNode Trie[];
// Check if the character is
// last character of a string or not
boolean isEnd;
// Constructor function
public TrieNode()
{
Trie = new TrieNode[256];
for(int i = 0; i < 256; i++)
{
Trie[i] = null;
}
isEnd = false;
}
}
class GFG{
// Function to insert a string into Trie
static void InsertTrie(TrieNode root, String s)
{
TrieNode temp = root;
// Traverse the string, s
for(int i = 0; i < s.length(); i++)
{
if (temp.Trie[s.charAt(i)] == null)
{
// Initialize a node
temp.Trie[s.charAt(i)] = new TrieNode();
}
// Update temp
temp = temp.Trie[s.charAt(i)];
}
// Mark the last character of
// the string to true
temp.isEnd = true;
}
// Function to print suggestions of the string
static void printSuggestions(TrieNode root, String res)
{
// If current character is
// the last character of a string
if (root.isEnd == true)
{
System.out.print(res + " ");
}
// Iterate over all possible
// characters of the string
for(int i = 0; i < 256; i++)
{
// If current character
// present in the Trie
if (root.Trie[i] != null)
{
// Insert current character
// into Trie
res += (char)i;
printSuggestions(root.Trie[i], res);
res = res.substring(0, res.length() - 2);
}
}
}
// Function to check if the string
// is present in Trie or not
static boolean checkPresent(TrieNode root, String key)
{
// Traverse the string
for(int i = 0; i < key.length(); i++)
{
// If current character not
// present in the Trie
if (root.Trie[key.charAt(i)] == null)
{
printSuggestions(root, key.substring(0, i));
return false;
}
// Update root
root = root.Trie[key.charAt(i)];
}
if (root.isEnd == true)
{
return true;
}
printSuggestions(root, key);
return false;
}
// Driver Code
public static void main(String[] args)
{
// Given array of strings
String str[] = { "gee", "geeks", "ape", "apple",
"geeksforgeeks" };
String key = "geek";
// Initialize a Trie
TrieNode root = new TrieNode();
// Insert strings to trie
for(int i = 0; i < str.length; i++)
{
InsertTrie(root, str[i]);
}
if (checkPresent(root, key))
{
System.out.println("YES");
}
}
}
// This code is contributed by Dharanendra L V.
Producción:
geeks geeksforgeeks
Complejidad de Tiempo: O(N * M), donde M es la longitud máxima de la string
Espacio Auxiliar: O(N * 256)