我无法理解一个线索的概念。从线索维基百科条目我看到这样的画面：

I'm having trouble understanding the concept of a trie. From the "trie" wikipedia entry I have this picture:

如果我看到这个正确的，在特里的所有叶节点将整个单词拼写和所有的父节点担任领导了最后的叶节点的角色。所以，如果我有一类称为DigitalTreeNode通过

If I see this correctly, all leaf nodes in a trie will have the entire word spelled out and all parent nodes hold the characters leading up the the final leaf node. So, if I have a class called DigitalTreeNode defined by

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

如果我想要实现返回的线索中最长的单词将它简单地涉及寻找最长的单词，在每个叶节点的方法？我怎么会实现的方法，如：

If I wanted to implement a method that returns the longest word in the trie would it simply involve finding the longest word at each leaf node? How would I implement a method such as:

public static String longestWord (DigitalTreeNode d);

我猜测它涉及到建立一个最长的字符串变量，递归经历的每个节点，并检查它是否是一个词，如果它是一个词，它的长度大于最长的变量则最长= newWordLength。但是，我不知道该地图孩子如何适应，如何将我发现使用上述方法中最长的单词在任何线索？

I'm guessing it involves setting up a longest String variable, recursively going through each node and checking if it is a word, if it is a word and it's length is greater than the longest variable then longest = newWordLength . But, I'm not sure how the Map children fits in. How would I find the longest word in any trie using the method above?

推荐答案

叶子节点不包含整个字符串通常（尽管他们可以），很多时间在一个线索，叶节点只包含一个$符号，以表明这是字符串的结尾。

The leaf nodes do not contain the entire string usually (though they can), many time in a trie, a leaf node just contains a '$' sign to indicate this is the end of the string.

要找到最长的单词的线索，你可以使用 BFS 上树，先找到最后叶。而最后一片叶子，是被弹出了BFS队列（之后被弹出BFS的算法与空队列停止）的最后一个元素。 要从此叶子，你需要从叶子上回到根得到实际的单词。 这个线程讨论如何可以做到

To find the longest word in a trie you can use a BFS on the tree, to first find the "last" leaf. The "last leaf" is the last element that was popped out of the BFS queue (after it was popped the algorithm of BFS stopped with an empty queue). To get the actual word from this leaf you will need to go up from the leaf back to the root. This thread discussed how it can be done.

这个解决方案是 O（| S | * N），其中 | S | 是平均长度一个字符串，而 N 是串在DS的数量。

This solution is O(|S| * n), where |S| is the average length of a string, and n is the number of string in the DS.

如果你可以操纵线索DS，我认为这是可以做到更好的（但似乎没有在这个问题的问题）

If you can manipulate the trie DS, I assume it can be done better (but it seems not to be the issue in this question)

伪code：

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