Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.

For example, if words = ["abc", "xyz"]&nbsp;and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.

Implement the StreamChecker class:


	StreamChecker(String[] words) Initializes the object with the strings array words.
	boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.


&nbsp;
Example 1:

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

Explanation
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
streamChecker.query("e"); // return False
streamChecker.query("f"); // return True, because 'f' is in the wordlist
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


&nbsp;
Constraints:


	1 &lt;= words.length &lt;= 2000
	1 &lt;= words[i].length &lt;= 200
	words[i] consists of lowercase English letters.
	letter is a lowercase English letter.
	At most 4 * 104 calls will be made to query.


class TrieNode:
    
    def __init__(self):
        self.children = {}
        self.endOfWord = False

class StreamChecker:

    def __init__(self, words: List[str]):
        self.root = TrieNode()
        self.qCur = self.root
        self.stream = collections.deque()
        cur = self.root
        for word in words:
            for i in range(len(word) - 1, -1, -1):
                ch = word[i]
                if ch not in cur.children:
                    cur.children[ch] = TrieNode()
                cur = cur.children[ch]
            cur.endOfWord = True
            cur = self.root

    def query(self, letter: str) -> bool:
        self.stream.appendleft(letter)
        cur = self.root
        for ch in self.stream:
            if ch not in cur.children:
                return False
            else:
                cur = cur.children[ch]
                if cur.endOfWord:
                    return True
        return False
class StreamChecker {
    
    class TrieNode {
        boolean isWord;
        TrieNode[] next = new TrieNode[26];
    }
    
    TrieNode root = new TrieNode();
    StringBuilder sb = new StringBuilder();
    
    public StreamChecker(String[] words) {
        createTrie(words);
    }
    
    public boolean query(char letter){
        sb.append(letter);
        TrieNode node = root;
        for(int i=sb.length()-1; i>=0 && node!=null; i--){
            char ch = sb.charAt(i);
            node = node.next[ch - 'a'];
            if(node != null && node.isWord){
                return true;
            }
        }
        return false;
    }
    
   private void createTrie(String words[]){
       for(String s : words){
           TrieNode node = root;
           int len = s.length();
           for(int i = len-1; i>=0; i--){
               char ch = s.charAt(i);
               if(node.next[ch-'a'] == null){
                   node.next[ch - 'a'] = new TrieNode();
               }
               node = node.next[ch - 'a'];
           }
           node.isWord = true;
       }
   }
}
class StreamChecker {
    struct Trie {
        Trie* suffixLink; //this is where it will fallback to when a letter can't be matched
        int id = -1; //this id will be 0 or greater if it matches a word
        map<char, Trie*> next;
    };
public:
    Trie* root;
    Trie* queryPtr;
    int uniqueIds = 0; //used to count all the unique words discovered and as part of the Trie id system
    
    StreamChecker(vector<string>& words) {
        root = new Trie();
        
		//standard trie traversal but keeping track of new words via id system
        for (string& word: words) {
            Trie* p = root;
            for (char c: word) {
                if (p->next.find(c) == p->next.end()) {
                    p->next.insert({ c, new Trie() });
                }
                p = p->next.at(c);
            }
            if (p->id == -1) {
                p->id = uniqueIds++;
            }
        }
        
        queue<Trie*> q;
        for (pair<char, Trie*> itr: root->next) {
            q.push(itr.second);
            itr.second->suffixLink = root;
        }
        
		//BFS traversal to build the automaton
        while (q.size()) {
            Trie* curr = q.front();
            q.pop();
            for (pair<char, Trie*> e: curr->next) {
                char c = e.first;
                Trie* node = e.second;
				
                Trie* ptr = curr->suffixLink;
                while (ptr != root && ptr->next.find(c) == ptr->next.end()) {
                    ptr = ptr->suffixLink;
                }
				//find the next suffixLink if it matches the current character or fallback to the root
                node->suffixLink = ptr->next.find(c) != ptr->next.end() ? ptr->next.at(c) : root;
				
				//if the current suffixLink happens to also be a word we should store its id to make it quick to find
                if (node->suffixLink->id != -1) {
                    node->id = node->suffixLink->id;
                }
                q.push(node);
            }
        }
		//the query ptr will now track every new streamed character and can be used to quickly find words
        queryPtr = root;
    }
    
    bool query(char letter) {
		//if the next letter can't be found and we're not at the root, we'll trace back until we find the longest suffix that matches
        while (queryPtr != root && queryPtr->next.find(letter) == queryPtr->next.end()) {
            queryPtr = queryPtr->suffixLink;
        }
        queryPtr = queryPtr->next.find(letter) != queryPtr->next.end() ? queryPtr->next.at(letter) : root;
		//if any word is found it will have an id that isn't -1
        return queryPtr->id != -1;
    }
};
var StreamChecker = function(words) {
    function Trie() {
        this.suffixLink = null; //this is where it will fallback to when a letter can't be matched
        this.id = -1; //this id will be 0 or greater if it matches a word
        this.next = new Map(); //map of <char, Trie*>
    }
    this.root = new Trie();
    this.uniqueIds = 0; //used to count all the unique words discovered and as part of the Trie id system

    //standard trie traversal but keeping track of new words via id system
    for (const word of words) {
        let ptr = this.root;
        for (const c of word) {
            if (!ptr.next.has(c)) {
                ptr.next.set(c, new Trie());
            }
            ptr = ptr.next.get(c);
        }
        if (ptr.id === -1) {
            ptr.id = this.uniqueIds++;
        }
    }

    //BFS traversal to build the automaton
    const q = [];
    for (const [c, node] of this.root.next) {
        //all first level children should point back to the root when a match to a character fails
        node.suffixLink = this.root;
        q.push(node);
    }

    while (q.length) {
        const curr = q.shift();
        for (const [c, node] of curr.next) {

            let ptr = curr.suffixLink;
            while (ptr !== this.root && !ptr.next.has(c)) {
                ptr = ptr.suffixLink;
            }
            //find the next suffixLink if it matches the current character or fallback to the root
            node.suffixLink = ptr.next.get(c) ?? this.root;

            //if the current suffixLink happens to also be a word we should store its id to make it quick to find
            if (node.suffixLink.id !== -1) {
                node.id = node.suffixLink.id;
            }
            q.push(node);
        }
    }
    //the query ptr will now track every new streamed character and use it to match
    this.queryPtr = this.root;
};

StreamChecker.prototype.query = function(letter) {
    //the query ptr will now track every new streamed character and can be used to quickly find words
    while (this.queryPtr !== this.root && !this.queryPtr.next.has(letter)) {
        this.queryPtr = this.queryPtr.suffixLink;
    }
    this.queryPtr = this.queryPtr.next.get(letter) ?? this.root;
    //if any word is found it will have an id that isn't -1
    return this.queryPtr.id !== -1;
};
Stream of Characters