[LeetCode] 1032. Stream of Characters

 Problem : https://leetcode.com/problems/stream-of-characters/

This is an obvious Tire problem. It is difficult because it is hard to realize the edge cases at the first place.

We cannot assume one input word cannot be prefix of another input word.

Such as:  ["ab","ba","aaab","abab","baa"]

To cover all cases, we need to remember the last pointer of all valid prefixes.

class TrieNode {
    char letter = 0;
    boolean end = false;
    HashMap<Character, TrieNode> children = new HashMap();
}

class StreamChecker {
    TrieNode root = new TrieNode();
    Queue<TrieNode> queue = new LinkedList();
    
    public StreamChecker(String[] words) {
        for (int i = 0; i < words.length; i++) {
            TrieNode p = root;
            
            for (int j = 0; j < words[i].length(); j++) {
                if (p.children.containsKey(words[i].charAt(j))) {
                    p = p.children.get(words[i].charAt(j));
                } else {
                    TrieNode tmp = new TrieNode();
                    tmp.letter = words[i].charAt(j);
                    p.children.put(words[i].charAt(j), tmp);
                    p = tmp;
                }
            }
            
            p.end = true;
        }
    }
    
    public boolean query(char letter) {
        queue.offer(root);
        
        boolean found = false;
        Queue<TrieNode> next = new LinkedList();
        
        while (!queue.isEmpty()) {
            TrieNode p = queue.poll();
            
            if (p.children.containsKey(letter)) {
                next.offer(p.children.get(letter));
                if (p.children.get(letter).end) {
                    found = true;
                }
            }
        }
        
        queue = next;
        return found;
    }
}

However this process is not optimized.

A better solution is saving the prefixes backwards in Trie. Because all potential valid prefixes end with the same letter.

class TrieNode:
    def __init__(self, w = None):
        self.w = w
        self.children = {}
        self.end = False

class StreamChecker:

    def __init__(self, words: List[str]):
        self.root = TrieNode()
        self.max_len = 0
        self.stream = deque()
        
        for word in words:
            self.max_len = max(self.max_len, len(word))
            
            p = self.root
            
            for w in word[::-1]:
                if w not in p.children:
                    trie = Trie(w)
                    p.children[w] = trie
                    p = trie
                else:
                    p = p.children[w]
            
            p.end = True
                      

    def query(self, letter: str) -> bool:
        self.stream.append(letter)
        
        while len(self.stream) > self.max_len:
            self.stream.popleft()
        
        p = self.root
        
        for w in reversed(self.stream):
            
            if w in p.children:
                p = p.children[w]
                if p.end:
                    return True
            else:
                return False
                
        return False