Come trovare la parola più lunga in un trie?

Question

Ho difficoltà a capire il concetto di un trie. Dalla voce di Wikipedia "trie" Ho questa immagine:

Se vedo correttamente, tutti i nodi foglia in un trie avrà l'intera parola precisato e tutti i nodi genitore contenere i caratteri che precedono la foglia finale nodo. Quindi, se ho una classe denominata DigitalTreeNode definito da

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

Se avessi voluto implementare un metodo che restituisce la parola più lunga nel trie sarebbe semplicemente comportare trovare la parola più lunga in ciascun nodo foglia? Come potrei implementare un metodo come:

public static String longestWord (DigitalTreeNode d); 

Sto indovinando si tratta di creare una variabile stringa più lunga, in modo ricorsivo passando per ogni nodo e controllare se si tratta di una parola, se si tratta di una parola e la sua lunghezza è maggiore della variabile più lunga quindi più lunga = newWordLength. Ma non sono sicuro di come si adattino i bambini della mappa. Come troverei la parola più lunga in qualsiasi trie usando il metodo sopra?

Answer 1

I nodi foglia non contengono l'intera stringa di solito (anche se possono), molte volte in un trie, un nodo foglia contiene solo un segno "$" per indicare che questa è la fine della stringa.

Per trovare la parola più lunga in un trie è possibile utilizzare un albero BFS per trovare prima l'ultima foglia. L'ultima foglia è l'ultimo elemento estratto dalla coda BFS (dopo che l'algoritmo di BFS è stato interrotto con una coda vuota).
Per ottenere la parola effettiva da questa foglia è necessario risalire dalla foglia alla radice. This thread discusso di come può essere fatto.

Questa soluzione è O(|S| * n), dove |S| è la lunghezza media di una stringa e n è il numero di stringa nel DS.

Se è possibile manipolare i DS trie, presumo si può fare meglio (ma sembra non essere il problema in questa domanda)

Pseudo codice:

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