Как правильно проверить, существует ли префикс слова в дереве?

Question

В настоящее время у меня есть функция "searchPrefix" моего класса Trie, определенная так:

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;
}

Предполагается, что эта функция возвращает "true", когда входная строка является префиксом слова, которое существует внутри объекта trie. Вот класс TrieNode для справки:

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

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

Согласно этому онлайн-судье, я неправильно определяю, является ли данная входная строка префиксом. Кто-нибудь может пролить свет на то, почему это неправильный метод? Я думаю, что когда мы добираемся до узла, который является концом входной строки, если у узла есть дочерние элементы, это префикс какого-то другого слова, поэтому мы возвращаем true. Однако это, по-видимому, неверно.

Answer 1

Я думаю, что вы не обрабатываете случай, когда префикс является терминальным словом в три.

Например, предположим, что есть только одно слово hello в три. Ваша реализация вернет false для searchPrefix("hello"),

Чтобы это исправить, нужно проверить 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;
}