1032. Stream of Characters

build trie
T: O(nm), n is words list size, m is each word's length
S: O(nm)

query:
T: O(m), max word length

class StreamChecker {
    
    class TrieNode {
        Map<Character, TrieNode> sons;
        boolean isWord;
        TrieNode() {
            sons = new HashMap<>();
        }
    }
    private TrieNode root;
    StringBuilder sb;
    
    private void insert(String word) {
        TrieNode node = root;
        for (int i = word.length() - 1; i >= 0; i--) {
            char c = word.charAt(i);
            node.sons.putIfAbsent(c, new TrieNode());
            node = node.sons.get(c);
        }
        node.isWord = true;
    }

    // Store the words in the trie with reverse order, and check the query string from the end
    public StreamChecker(String[] words) {
        root = new TrieNode();
        sb = new StringBuilder();
        
        for (String word : words) {
            insert(word);
        }
    }
    
    public boolean query(char letter) {
        TrieNode node = root;
        sb.append(letter); // a, b, c, d -> d, c, b, a
        
        for (int i = sb.length() - 1; i >= 0; i--) {
            char c = sb.charAt(i);
            if (node.isWord) {
                return true;
            }
            if (node.sons.get(c) == null) {
                return false;
            }
            node = node.sons.get(c);
        }
        return node.isWord;
    }
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker obj = new StreamChecker(words);
 * boolean param_1 = obj.query(letter);
 
 trie 顛倒存
 
 Store the words in the trie with reverse order, and check the query string from the end
 
 
 這題意思是 query 時, 會把之前都輸入過的, 都放進去比對, 所以這就是 dcba, dc 就命中 "cd" 這個 sufix
 所以也要倒著便利
 
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // return False
streamChecker.query("b"); // return False
streamChecker.query("c"); // return False
streamChecker.query("d"); // return True, because 'cd' is in the wordlist

到 f 又命中

streamChecker.query("e"); // return False
streamChecker.query("f"); // return True, because 'f' is in the wordlist

到 l, 又命中
streamChecker.query("g"); // return False
streamChecker.query("h"); // return False
streamChecker.query("i"); // return False
streamChecker.query("j"); // return False
streamChecker.query("k"); // return False
streamChecker.query("l"); // return True, because 'kl' is in the wordlist

build
T: O(nm), n is words list size, m is each word's length
S: O(nm)

query:
T: O(m), max word length
S: O(m), srtringbuilder may append m word length
 */