如何在特里找到最长的单词？-Java 学习之路

我无法理解特里的概念 . 来自"trie"维基百科条目我有这张照片：
enter image description here

如果我正确地看到这一点，则特里结构中的所有叶节点将拼写出整个单词，并且所有父节点都保持通向最终叶节点的字符 . 所以，如果我有一个名为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 . 但是，我不确定 Map 中的孩子是如何适应的 . 如何使用上述方法找到任何特里结构中最长的单词？

2 回答

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

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

此解决方案是 O(|S| * n) ，其中 |S| 是字符串的平均长度， n 是DS中的字符串数 .

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

Pseudo 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
```
回复于 2024-06-02T20:21:23+08:00

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

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

在插入时，如果它是单词集boolean的结尾为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;
    }

回复于 2024-06-02T20:21:23+08:00

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

2 回答

相关问题