## Algorithm

Problem Name: 1032. Stream of Characters

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"]` 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`.

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
```

Constraints:

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

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class StreamChecker {

Deque stream;
TrieNode root;
public StreamChecker(String[] words) {
root = new TrieNode('-');
stream = new ArrayDeque<>();
}

TrieNode curr = root;
for (int i = word.length() - 1; i >= 0; i--) {
char c = word.charAt(i);
if (curr.children[c - 'a'] == null) {
curr.children[c - 'a'] = new TrieNode(c);
}
curr = curr.children[c - 'a'];
}
curr.isWord = true;
}

public boolean query(char letter) {
TrieNode curr = root;
for (char c : stream) {
if (curr.isWord) {
return true;
}
if (curr.children[c - 'a'] == null) {
return false;
}
curr = curr.children[c - 'a'];
}
return curr.isWord;
}

class TrieNode {
char c;
TrieNode[] children;
boolean isWord;

public TrieNode(char c) {
this.c = c;
children = new TrieNode[26];
}
}
}
``````
Copy The Code &

Input

cmd
["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

cmd
[null, false, false, false, true, false, true, false, false, false, false, false, true]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const StreamChecker = function(words) {
this.maxLen = 0
this.pos = -1
this.s = []
this.root = new Node()
for (let w of words) {
this.maxLen = Math.max(this.maxLen, w.length)
}
}

StreamChecker.prototype.query = function(letter) {
this.s[++this.pos] = letter
return this.find(this.s, this.pos, Math.min(this.pos + 1, this.maxLen))
}

let len = word.length
let p = this.root
for (let i = len - 1; i >= 0; i--) {
let k = word.charCodeAt(i) - 'a'.charCodeAt(0)
if (p.child[k] == null) p.child[k] = new Node()
p = p.child[k]
}
p.valid = true
}

StreamChecker.prototype.find = function(s, pos, len) {
let p = this.root
for (let i = 0; i < len; i++) {
let k = s[pos - i].charCodeAt(0) - 'a'.charCodeAt(0)
if (p.child[k] == null) return false
p = p.child[k]
if (p.valid) return true
}
return false
}
class Node {
constructor() {
this.child = []
this.valid = false
}
}
``````
Copy The Code &

Input

cmd
["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

cmd
[null, false, false, false, true, false, true, false, false, false, false, false, true]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
import functools
class StreamChecker(object):

def __init__(self, words):
T = lambda: collections.defaultdict(T)
self.trie = T()
for w in words: functools.reduce(dict.__getitem__, w, self.trie)['#'] = True
self.waiting = []

def query(self, letter):
self.waiting = [node[letter] for node in self.waiting + [self.trie] if letter in node]
return any("#" in node for node in self.waiting)
``````
Copy The Code &

Input

cmd
["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

cmd
[null, false, false, false, true, false, true, false, false, false, false, false, true]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _1032_StreamOfCharacters
{

public _1032_StreamOfCharacters(string[] words)
{
root = new Trie();
stream = new List();

foreach (var word in words)
{
var current = root;
foreach (var ch in new string(word.Reverse().ToArray()))
{
if (current.Children[ch - 'a'] == null)
current.Children[ch - 'a'] = new Trie();
current = current.Children[ch - 'a'];
}
current.IsFinished = true;
}
}

public bool Query(char letter)
{
var current = root;

for (int i = stream.Count - 1; i >= 0; i--)
{
if (current.IsFinished) return true;

if (current.Children[stream[i] - 'a'] == null)
return false;

current = current.Children[stream[i] - 'a'];
}

return current.IsFinished;
}

public class Trie
{
public Trie[] Children { get; } = new Trie[26];
public bool IsFinished { get; set; }
}
}

}
``````
Copy The Code &

Input

cmd
["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

cmd
[null, false, false, false, true, false, true, false, false, false, false, false, true]