Jak znaleźć najdłuższe słowo w trie?

Question

Mam problem ze zrozumieniem koncepcji trie. Z „trie” wpisu wikipedia mam to zdjęcie:

Jeśli widzę to poprawnie, wszystkie węzły liścia w trie będą mieli całe słowo wyjaśnienia i wszystkie węzły nadrzędne przytrzymaj znaki prowadzące do ostatecznego liść węzeł. Tak więc, jeśli mam klasy o nazwie DigitalTreeNode zdefiniowane przez

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

Gdybym chciał wdrożyć metodę, która zwraca najdłuższy wyraz w trie byłoby po prostu obejmować znalezienie najdłuższy wyraz w każdym węźle liści? Jak zaimplementować metody takie jak:

public static String longestWord (DigitalTreeNode d); 

Zgaduję, że obejmuje utworzenie zmiennej najdłuższy ciąg, rekursywnie przechodzi każdego węzła i sprawdzenie czy jest to słowo, jeśli jest to słowo i to długości jest większa niż najdłuższa zmienna, a następnie najdłuższa = nowa długość słowa. Ale nie jestem pewien, w jaki sposób dopasowują się dzieci z mapy. Jak znaleźć najdłuższe słowo w dowolnym triku, używając powyższej metody?

Answer 1

Węzły liści nie zawierają zwykle całego ciągu znaków (choć mogą), wiele czasu w kliencie, węzeł liści zawiera znak "$", który wskazuje, że jest to koniec ciągu.

Aby znaleźć najdłuższe słowo w trie można użyć drzewa BFS, aby najpierw znaleźć "ostatni" liść. "Ostatni liść" to ostatni element, który został wyrzucony z kolejki BFS (po tym jak został on zerwany, algorytm BFS zatrzymany z pustą kolejką).
Aby uzyskać rzeczywiste słowo z tego liścia, będziesz musiał przejść od liścia z powrotem do katalogu głównego. This thread omówiono, jak można to zrobić.

To rozwiązanie to O(|S| * n), gdzie |S| to średnia długość ciągu, a n to numer ciągu w DS.

Jeśli można manipulować TRIE DS, zakładam, że można to zrobić lepiej (ale nie wydaje się być problemem w tej kwestii)

Pseudo kod:

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