leetCode：1032. Stream of Characters

leetCode の「1032. Stream of Characters」を解いた。
https://leetcode.com/problems/stream-of-characters/

Trie木の実装の良い練習になったので、今後の参考のために自分の解答をここに残しておく。なお、通常の Trie 木と異なり、この問題では、単語を逆向きに格納し、単語検索の際にも逆から検索している。

import java.util.HashMap;
import java.util.Map;

class StreamChecker {

    TrieNode root = new TrieNode();

    // queries への追加を繰り返すので、性能面を考慮し、
    // String ではなく、StringBuilder を使っている。
    StringBuilder queries = new StringBuilder();

    public StreamChecker(String[] words) {
        createTrie(words);
    }

    private void createTrie(String[] words) {
        for (String word : words) {
            TrieNode curNode = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                char ch = word.charAt(i);
                TrieNode child = curNode.getChildNodes().get(ch);
                if (child == null) {
                    // ch は子 Node として持っていないので新規作成。
                    TrieNode newNode = new TrieNode();
                    curNode.getChildNodes().put(ch, newNode);
                    curNode = newNode;
                }
                else {
                    // ch は既に子 Node として持っているので何もしない (ポインタを進めるだけ)
                    curNode = child;
                }
            }
            curNode.setWord(true);
        }
    }

    public boolean query(char letter) {
        TrieNode curNode = root;
        queries.append(letter);

        for (int i = queries.length() - 1; i >= 0; i--) {
            TrieNode child = curNode.getChildNodes().get(queries.charAt(i));
            if (child == null) {
                return false;
            }
            if (child.isWord()) {
                return true;
            }
            curNode = child;
        }

        // ここまで来たということは、queries を走査しきったが、
        // Trie 木の中で対象の単語がなかったということ。
        return false;
    }

    private static class TrieNode {
        //「後続の文字 → 後続の文字に対応する子 Node」のマップ
        // 例えば、「root -> "a" -> "p" -> "p" -> "l" -> "e"」というツリーがあったとして、
        // "a" のノードにいる時、"p" を key とする子 Node があれば、"ap" までは持っていると判断する。
        private Map<Character, TrieNode> childNodes = new HashMap<>();

        // このノードが単語かどうかのフラグ
        private boolean isWord = false;

        private Map<Character, TrieNode> getChildNodes() {
            return childNodes;
        }

        private boolean isWord() {
            return isWord;
        }

        private void setWord(boolean word) {
            isWord = word;
        }
    }
}