Сбор всех слов в Trie на Java

Question

Я пытаюсь реализовать метод, который будет добавлять все слова из Trie в список. Я использую Hashmap для хранения символьного и ссылочного узла дочернего узла. Символы должны включать только буквы a-z. Это моя реализация узла:

class Node {
    char c;
    HashMap<Character, Node> children = new HashMap<>();
    boolean isCompleteWord;

    public Node(char c){
        this.c = c;
        isCompleteWord = false;
    }
    public Node(){}
}

Я не совсем уверен, с чего начать, листовой узел сможет сказать мне, завершено ли слово, поэтому я мог пройти по Trie до конечного узла и добавить символы в строку возможно, но как только это слово будет добавлено, как я могу пройти через различные ветви дерева, чтобы добавить другие слова?

Answer 1

обо всем по порядку. На самом деле вам не нужно хранить символьный атрибут в вашем классе узлов, поскольку он уже неявно хранится в атрибуте children его родительского узла.
Таким образом, ваш класс Node на самом деле может быть:

class Node {
    HashMap<Character, Node> children = new HashMap<>();
    boolean isCompleteWord;

    public Node(){
        isCompleteWord = false;
    }
}

Кроме того, как и всем корневым деревьям, вашему Trie потребуется корень. Вам понадобится рут, прежде чем хранить любое слово в вашем Trie.

root = new Node();

Корневой узел представляет собой пустую строку, поэтому, если вам нужно сохранить ее, вам нужно будет проверить атрибут isCompleteWord root.

Затем, чтобы вставить слово, скажем, myWord, вам нужно начать с корня и применить следующее правило:
- Рассмотрим первую букву myWord [0], скажем 'c'. Вам нужно различить 2 случая, независимо от того, содержит ли root ключ «c» или нет. Если оно не содержит слова, вам нужно будет создать новый узел в вашем Trie. В противном случае вам просто нужно продолжать «ходить» по веткам.
- Как только вы прибудете на последнюю букву, вам нужно будет только установить атрибут isCompleteWord на true. Вот возможная (полностью непроверенная) реализация addWord, которая добавляет слово в Trie и возвращает true, если оно уже было, false в противном случае.

public bool addWord(Node node, String word, int idx){        
    if (idx == word.length() -1){ 
    // we're checking the last letter
        bool result = node.isCompleteWord;
        node.isCompleteWord = true;
        return result;
    } else {
        if (!node.children.containsKey(word.charAt(idx)){ 
        // no child with this letter, create one
            child = new Node()
            node.children.put(word.charAt(idx), child);
        } 
        return addWord(node.children(word.charAt(idx)), word, idx+1);
    }
}

Чтобы добавить слово, скажем, myWord, в три, вам нужно только назвать его следующим образом:

addWord(root, myWord, 0);

Функция, которая проверяет, сохранено ли слово в дереве, очень похожа на ту, которая добавляет слова.

public bool containsWord(Node node, String word, int idx){        
    if (idx == word.length() -1){ 
        return node.isCompleteWord;
    } else {
        if (!node.children.containsKey(word.charAt(idx)){ 
        // no child with this letter, the word is not in the trie
            return false;
        } else {
            return containsWord(node.children(word.charAt(idx)), word, idx+1);
        }
    }
}