如何在特里找到最长的单词？

Question

我无法理解特里的概念.从"特里"维基百科条目我有这张图片:

如果我正确地看到这一点,则特里结构中的所有叶节点将拼写出整个单词,并且所有父节点都保持通向最终叶节点的字符.所以,如果我有一个名为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);

我猜它涉及设置一个最长的String变量,递归遍历每个节点并检查它是否是一个单词,如果它是一个单词并且它的长度大于最长变量那么longest = newWordLength.但是,我不确定地图中的孩子是如何适应的.如何使用上述方法找到任何特里结构中最长的单词？

Answer 1

叶子节点通常不包含整个字符串(尽管它们可以),在trie中很多时候,叶子节点只包含一个'$'符号来表示这是字符串的结尾.

要查找特里结构中最长的单词,您可以在树上使用BFS,首先找到"最后"的叶子."最后一个叶子"是从BFS队列中弹出的最后一个元素(在弹出BFS算法后,空队列停止).
要从这片叶子中获取实际的单词,您需要从叶子上升到根.这个主题讨论了如何做到这一点.

这个解决方案是O(|S| * n),|S|字符串的平均长度在哪里,是nDS中字符串的数量.

如果你可以操纵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