如何在字典树中找到最长的单词？

Question

我在理解trie的概念方面遇到了困难。从维基百科的“trie”词条中，我得到了这张图片：

如果我理解正确的话，在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树中最长单词的方法，是否只需要在每个叶节点找到最长的单词？如何实现这样的方法：

```java public String findLongestWord() { // implementation goes here } ```

public static String longestWord (DigitalTreeNode d);

我猜测它涉及设置一个最长的字符串变量，递归地遍历每个节点并检查它是否是一个单词，如果它是一个单词并且它的长度大于最长变量，则最长变量=新单词长度。但是，我不确定Map子元素如何适合其中。使用上述方法如何找到任何trie中最长的单词？

- user1766888

---

你要寻找什么样的复杂度？对结构进行广度优先搜索[BFS]可以在O(|S|*n)的时间内轻松找到它，其中|S|是平均字符串长度。我认为使用标准trie树无法更好地完成此任务，但如果你能操作数据结构，可能会有更好的方法。 - amit

查看每个字符串的字符，并假设它们有|S|个字符长，我认为我无法比O（|S| * n）复杂度更好。 - user1766888

Answer 1

叶节点通常不包含整个字符串（虽然它们可以），在 trie 中，很多时候，叶节点只包含一个“$”符号，以表示这是字符串的结尾。

要在 trie 中找到最长的单词，您可以对树进行 BFS，以首先找到“最后一个”叶子。 “最后一个叶子”是从 BFS 队列中弹出的最后一个元素（在弹出 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

- amit

Answer 2

另一种方法是添加一个布尔值来表示它是否为单词的结尾和实际单词，如下所示：

 public class TrieNode {
        private HashMap<Character, TrieNode> children = new HashMap<>();
        private boolean endOfWord;
        private String actualWord;
        //setter getter
}

在插入时，如果它是单词结尾，则将布尔值设置为 true 和实际单词

 public void insert(String insert) {
        HashMap<Character, TrieNode> parent = root.getChildren();
        TrieNode child = null;
        for (Character c : insert.toCharArray()) {
            child = parent.containsKey(c) ? parent.get(c) : new TrieNode();
            parent.put(c, child);
            parent = child.getChildren();

        }
        if (child != null) {
            child.setEndOfWord(true);
            child.setActualWord(insert);
        }
    }

最后，只需进行BFS搜索即可获取它，一旦您拥有该节点，您就拥有了实际要查找的单词。

  public TrieNode findLongest() {
        LinkedList<TrieNode> queue = new LinkedList();
        queue.push(root);
        TrieNode current = null;
        while (!queue.isEmpty()) {
            current = queue.pop();
            if (current.getChildren() != null) {
                for (TrieNode children : current.getChildren().values()) {
                    queue.push(children);
                }
            }
        }
        System.out.println(current.getActualWord()); // check here
        return current;
    }

- mel3kings