Trie structure de données et de recherche efficace en Java

Question

J'ai une tâche sur la structure de données et la recherche efficace. Le premier paramètre d'entrée est un gros fichier texte qui contient des chaînes, chaque ligne est une nouvelle chaîne. Le deuxième paramètre d'entrée est un préfixe. La sortie est le mot le plus court trouvé dans ce gros fichier qui commence par le préfixe donné. Donc, j'ai utilisé HashMap et construit un Trie en utilisant chaque lettre comme une clé. Donc, je fais juste un coup d'oeil au lieu de l'itération, ce qui économise du temps et de la mémoire. La seule chose qui ne me semble pas bonne est la recherche du mot le plus court. Je veux dire maintenant que je reçois la liste des mots qui commencent par le préfixe donné. Et puis je cherche le plus court en parcourant la liste. Y a-t-il un autre moyen d'obtenir le mot le plus court? Toutes les suggestions pour améliorer cela sont vraiment appréciées car c'est la première fois de ma vie que je travaille avec Trie. S'il vous plaît, voir mon code ci-dessous:

TrieNode

class TrieNode { 

HashMap<Character, TrieNode> child; 

boolean isLast; 

public TrieNode() { 
    child = new HashMap<Character, TrieNode>(); 
    // Initialize all the Trie nodes with NULL 
    for (char i = 'a'; i <= 'z'; i++) 
     child.put(i, null); 
    isLast = false; 
}} 

Trie

public class Trie { 

TrieNode root = new TrieNode(); 
ArrayList<String> words = new ArrayList<>(); 

public void insertIntoTrie(ArrayList<String> newWords) { 

    int n = newWords.size(); 
    for (int i = 0; i < n; i++) { 
     insert(newWords.get(i)); 
    }} 


public void getWordsList(TrieNode curNode, 
         String prefix) { 

    if (curNode != null) { 

     if (curNode.isLast) 
      words.add(prefix); 

     for (char i = 'a'; i <= 'z'; i++) { 
      TrieNode nextNode = curNode.child.get(i); 
      if (nextNode != null) { 
       getWordsList(nextNode, prefix + i); 
      }}}} 


public void getShortest(String str) { 
    TrieNode prevNode = root; 
    TrieNode found = null; 

    String prefix = ""; 
    int len = str.length(); 

    for (int i = 0; i < len; i++) { 

     prefix += str.charAt(i); 

     char lastChar = prefix.charAt(i); 

     TrieNode curNode = prevNode.child.get(lastChar); 
     found = curNode; 

     if (curNode == null) { 
      System.out.println("No Results Found!"); 
      i++; 
      break;} 
    prevNode = curNode; } 

    getWordsList(found, prefix); 

    if (words.size() != 0) { 

     String shortestWord = words.get(0); 

     for (int j = 1; j < words.size(); j++) { 
      String nextWord = words.get(j); 
      if (nextWord.compareTo(shortestWord) < 0) { 
       shortestWord = nextWord; 

      }} 

     System.out.println("The shortest word is: " + shortestWord); 
    }}} 

Answer 1

À moins que vous devez enregistrer tous les mots pertinents, il n'y a aucune raison pour les sauver dans une HashMap. En outre, un HashMap est pratiquement inutile pour l'itération, puisque vous devez accéder à chaque mot de toute façon. Pour votre problème spécifique, je suggère d'utiliser une recherche min simple, c'est-à-dire de rechercher le préfixe et chaque fois que vous le parcourez, enregistrez-le seulement s'il est plus court que le mot que vous avez actuellement stocké.