如何在trie中找到最长的单词？

Question

如果我正确地看到了这一点，那么trie中的所有叶节点都将拼写出整个单词，所有父节点都包含最终叶节点之前的字符。因此，如果我有一个名为DigitalTreeNode的类，其定义为

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

如果我想实现一个返回trie中最长单词的方法，是否只需要在每个叶节点查找最长单词？如何实现方法，例如：

public static String longestWord (DigitalTreeNode d);

我猜它涉及到设置一个最长的字符串变量，递归地遍历每个节点，并检查它是否是一个单词，如果它是一个单词，并且它的长度大于最长的变量，那么lengte=newWordLength。但是，我不确定地图儿童如何适应。我如何使用上面的方法在任何trie中找到最长的单词？

Answer 1

叶节点通常不包含整个字符串（尽管它们可以），在trie中，叶节点通常只包含一个'$'符号来表示这是字符串的结尾。

要在trie中找到最长的单词，可以在树上使用BFS，首先找到“最后”的叶子。“last leaf”是从BFS队列中弹出的最后一个元素（在它弹出之后，BFS的算法将以空队列停止）。
要从这片叶子中获得实际的单词，您需要从叶子向上返回到树根。本文讨论了如何做到这一点。

这个解决方案是O(S*n)，其中S是字符串的平均长度，n是DS中字符串的数目。

如果你能操纵trie DS，我认为它可以做得更好（但这似乎不是这个问题的问题）

伪代码：

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