5

我无法理解 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 中最长单词的方法，它是否只涉及在每个叶节点处查找最长单词？我将如何实现一种方法，例如：

public static String longestWord (DigitalTreeNode d);

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

4

2 回答 2

6

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

要在树中找到最长的单词，您可以在树上使用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
于 2012-11-02T08:53:16.823 回答
0

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

 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;
    }
于 2018-12-21T12:56:03.930 回答