Corrector ortográfico usando Trie

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)

Publicación traducida automáticamente

Artículo escrito por tk315 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *