如何正确检查 trie 中是否存在单词前缀？

Question

目前我的 Trie class 的 "searchPrefix" 函数定义如下：

public Boolean searchPrefix(String word) {
    TrieNode temp = this.root;
    for(int i = 0; i < word.length(); i++){
        if(temp.children.get(word.charAt(i)) == null) return false;
        else temp = temp.children.get(word.charAt(i));
    }
    return (temp.children.isEmpty()) ? false : true;
}

当输入字符串是 trie 对象中存在的单词的前缀时，此函数应该 return "true"。这里是TrieNodeclass供参考：

class TrieNode {
   Character c;
   Boolean isWord = false;
   HashMap<Character, TrieNode> children = new HashMap<>();

   public TrieNode() {}
   public TrieNode(Character c) {
    this.c = c;
   }
}

根据这个在线判断，我错误地判断给定的输入字符串是否为前缀。谁能阐明为什么这是不正确的方法？我的想法是，当我们到达输入字符串末尾的节点时，如果该节点有子节点，则它是某个其他单词的前缀，因此我们 return 为真。然而这显然是不正确的。

Answer 1

我认为您没有处理前缀是 trie 中的终结词的情况。

例如，假设一个 trie 中只有一个词 hello。对于 searchPrefix("hello").

，您的实施将为 return false

要修复它，您还需要检查 isWord 标志：

public Boolean searchPrefix(String word) {
    TrieNode temp = this.root;
    for (int i = 0; i < word.length(); i++){
        TrieNode next = temp.children.get(word.charAt(i));
        if (next == null) {
            return false;
        }
        temp = next;
    }
    return !temp.children.isEmpty() || temp.isWord;
}

如何正确检查 trie 中是否存在单词前缀？

How to properly check if a prefix of a word exists in a trie?

java

trie