Programa Java para implementar Hash Trie

Un trie no es algo en lo que los estudiantes de informática hayan pasado tanto tiempo en la universidad, pero es realmente muy importante para las entrevistas. Un trie es una estructura de datos que en realidad es un tipo de árbol, pero a menudo se usa para almacenar una array asociativa o un conjunto dinámico donde las claves suelen ser caracteres o strings, y su posición en el árbol define la clave con la que está asociado. . La forma en que funciona es que cada sucesor de un Node tiene un prefijo común de la string asociada con ese Node, lo que significa que cada Node puede almacenar un, solo un carácter como sus datos, pero luego, si observamos la ruta desde la raíz hasta ese Node, esa nota realmente representa una palabra o una parte de una palabra, y lo que nos permite hacer es búsquedas muy rápidas de un tipo particular de palabra o carácter.

Código Java:

• Importación del módulo requerido:

import java.io.*;
import java.util.*;

• Ahora, haremos una clase TrieHash en la que implementaremos un HashMap, también contendrá dos constructores con cero y un solo argumento de array, una función para agregar caracteres al hash trie y una función para buscar la string específica en el hash trie .

class TrieHash {
  
    // implementing a HashMap
    private HashMap<Character, HashMap> origin;
  
    // implementing a zero-argument constructor
    public TrieHash()
    {
        // creating a new HashMap
        origin = new HashMap<Character, HashMap>();
    }
  
    // implementing another constructor
    // with an array as a parameter
    public TrieHash(String[] array)
    {
        origin = new HashMap<Character, HashMap>();
        // attaching that array string in the trie
        for (String c : array)
            attach(c);
    }
  
    // attach function to add character to the trie
    public void attach(String str)
    {
        HashMap<Character, HashMap> node = origin;
        int i = 0;
        while (i < str.length()) {
            // if node already contains that key,
            //  we will simply point that node
            if (node.containsKey(str.charAt(i))) {
                node = node.get(str.charAt(i));
            }
            else {
  
                // else we will make a new hashmap with
                // that character and then point it.
                node.put(str.charAt(i),
                         new HashMap<Character, HashMap>());
                node = node.get(str.charAt(i));
            }
            i++;
        }
  
        // putting 0 to end the string
        node.put('\0', new HashMap<Character, HashMap>(0));
    }
  
    // function to search for the specific
    // string in the hash trie
    public boolean search(String str)
    {
        HashMap<Character, HashMap> presentNode = origin;
        int i = 0;
        while (i < str.length()) {
  
            // will search for that character if it exists
            if (presentNode.containsKey(str.charAt(i))) {
                presentNode
                    = presentNode.get(str.charAt(i));
            }
            else {
                // if the character does not exist
                // that simply means the whole string
                // will also not exists, so we will
                // return false if we find a character
                // which is not found in the hash trie
                return false;
            }
            i++;
        }
        // this will check for the end string,
        // and if the whole string is found,
        // it will return true else false
        if (presentNode.containsKey('\0')) {
            return true;
        }
        else {
            return false;
        }
    }
}

Ahora todas las funciones requeridas están codificadas, ahora probaremos esas funciones con la entrada del usuario. Para esto, nuevamente crearemos una nueva clase para probar nuestro hash trie que le pedirá al usuario que ingrese las palabras para trie y la palabra que se buscará.

public class Main {
    // unreported exception IOException must be caught or
    // declared to be thrown
    public static void main(String[] args)
        throws IOException
    {
        BufferedReader br
            = new BufferedReader(new InputStreamReader(
                System.in)); // this will accepts the words
                             // for the hash trie
        System.out.println(
            "Enter the words separated with space to be entered into trie");
  
        // will read the line which user will
        // provide with space separated words
        String input = br.readLine();
  
        // it will split all the words
        // and store them in the string array
        String[] c = input.split(" ");
  
        // now we will use constructor with string array as
        // parameter and we will pass the user entered
        // string in that constructor to construct the hash
        // trie
        TrieHash trie = new TrieHash(c);
        System.out.println(
            "\nEnter the word one by one to be searched in hash-trie");
        String word = br.readLine();
  
        // this will search for the word in out trie
        if (trie.search(word)) {
            System.out.println("Word Found in the trie");
        }
        else {
            System.out.println(
                "Word NOT Found in the trie!");
        }
    }
}

A continuación se muestra la implementación del enunciado del problema:

import java.io.*;
import java.util.*;
  
class TrieHash {
  
    // implementing a HashMap
    private HashMap<Character, HashMap> origin;
  
    // implementing a zero-argument constructor
    public TrieHash()
    {
  
        // creating a new HashMap
        origin = new HashMap<Character, HashMap>();
    }
  
    // implementing another constructor
    // with an array as a parameter
    public TrieHash(String[] array)
    {
        origin = new HashMap<Character, HashMap>();
        // attaching that array string in the trie
        for (String c : array)
            attach(c);
    }
  
    // attach function to add
    // character to the trie
    public void attach(String str)
    {
        HashMap<Character, HashMap> node = origin;
        int i = 0;
        while (i < str.length()) {
            // if node already contains thatkey,
            // we will simply point that node
            if (node.containsKey(str.charAt(i))) {
                node = node.get(str.charAt(i));
            }
            else {
                // else we will make a new hashmap with
                // that character and then point it.
                node.put(str.charAt(i),
                         new HashMap<Character, HashMap>());
                node = node.get(str.charAt(i));
            }
            i++;
        }
  
        // putting 0 to end the string
        node.put('\0', new HashMap<Character, HashMap>(0));
    }
  
    // function to search for the
    // specific string in the hash trie
    public boolean search(String str)
    {
        HashMap<Character, HashMap> presentNode = origin;
        int i = 0;
        while (i < str.length()) {
            // will search for that character
            // if it exists
            if (presentNode.containsKey(str.charAt(i))) {
                presentNode
                    = presentNode.get(str.charAt(i));
            }
            else {
                // if the character does notexist that
                // simply means the whole string will
                // also not exists, so we will return
                // false if we find a character which
                // is not found in the hash trie
                return false;
            }
            i++;
        }
        // this will check for the end string,
        // and if the whole string is found,
        // it will return true else false
        if (presentNode.containsKey('\0')) {
            return true;
        }
        else {
            return false;
        }
    }
}
  
public class Main {
    // unreported exception IOException
    // must be caught or declared to be thrown
    public static void main(String[] args)
        throws IOException
    {
  
        // this will accepts the words for the hash trie
        BufferedReader br = new BufferedReader(
            new InputStreamReader(System.in));
        System.out.println(
            "Enter the words separated with space to be entered into trie");
        // will read the line which user will
        // provide with space separated words
        String input = br.readLine();
  
        // it will split all the words and
        // store them in the string array
        String[] c = input.split(" ");
  
        // now we will use constructor with string
        // array as parameter and we will pass the
        // user entered string in that constructor
        // to construct the hash trie
        TrieHash trie = new TrieHash(c);
        System.out.println(
            "How many words you have to search in the trie");
        String count = br.readLine();
        int counts = Integer.parseInt(count);
        for (int i = 0; i < counts; i++) {
            System.out.println(
                "\nEnter the word one by one to be searched in hash-trie ");
            String word = br.readLine();
            // this will search for the word in out trie
            if (trie.search(word)) {
                System.out.println(
                    "Word Found in the trie");
            }
            else {
                System.out.println(
                    "Word NOT Found in the trie!");
            }
        }
    }
}

Salida1:

Salida2: