Comment trouver le mot le plus long dans un trie?

Question

J'ai de la difficulté à comprendre le concept de trie. A partir de l'entrée de wikipedia « de Trie » J'ai cette image:

Si je vois correctement, tous les nœuds feuilles dans une structure arborescente aura le mot entier énoncé et tous les nœuds parents tenir les personnages qui ont précédé la la feuille finale nœud. Donc, si j'ai une classe appelée DigitalTreeNode définie par

public class DigitalTreeNode { 
     public boolean isAWord; 
     public String wordToHere; (compiles all the characters in a word together) 
     public Map<String, DTN> children; 
} 

Si je voulais mettre en œuvre une méthode qui renvoie le mot le plus long dans la structure arborescente serait-il simplement impliquer de trouver le mot le plus long à chaque noeud de feuille? Comment puis-je mettre en œuvre une méthode telle que:

public static String longestWord (DigitalTreeNode d); 

Je devine que cela implique d'une plus longue variable de chaîne, allant récursive à travers chaque nœud et vérifier si elle est un mot, si elle est un mot et sa longueur est supérieur à la plus longue variable puis plus long = newWordLength. Mais, je ne suis pas sûr de savoir comment les enfants de la carte s'intègre. Comment pourrais-je trouver le mot le plus long dans un trie en utilisant la méthode ci-dessus?

Answer 1

Les nœuds feuille ne contiennent généralement pas la chaîne entière (bien qu'ils le puissent), beaucoup de fois dans un trie, un nœud feuille contient juste un signe '$' pour indiquer que c'est la fin de la chaîne.

Pour trouver le mot le plus long dans un trie, vous pouvez utiliser un BFS sur l'arbre, pour trouver d'abord la "dernière" feuille. La "dernière feuille" est le dernier élément qui a été sorti de la file d'attente BFS (après l'apparition de l'algorithme de BFS arrêté avec une file d'attente vide).
Pour obtenir le mot actuel de cette feuille vous aurez besoin de remonter de la feuille à la racine. This thread discuté comment cela peut être fait.

Cette solution est O(|S| * n), où |S| est la longueur moyenne d'une chaîne, et n est le nombre de chaîne dans le DS.

Si vous pouvez manipuler la DS Trie, je suppose que cela peut être fait mieux (mais il ne semble pas être le problème dans cette question)

Code Pseudo:

findLongest(trie): 
    //first do a BFS and find the "last node" 
    queue <- [] 
    queue.add(trie.root) 
    last <- nil 
    map <- empty map 
    while (not queue.empty()): 
    curr <- queue.pop() 
    for each son of curr: 
     queue.add(son) 
     map.put(son,curr) //marking curr as the parent of son 
    last <- curr 
    //in here, last indicate the leaf of the longest word 
    //Now, go up the trie and find the actual path/string 
    curr <- last 
    str = "" 
    while (curr != nil): 
     str = curr + str //we go from end to start 
     curr = map.get(curr) 
    return str