Algorithm
Problem Name: 1032. Stream of Characters
Problem Link: https://leetcode.com/problems/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 arraywords.boolean query(char letter)Accepts a new character from the stream and returnstrueif any non-empty suffix from the stream forms a word that is inwords.
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 <= 20001 <= words[i].length <= 200words[i]consists of lowercase English letters.letteris a lowercase English letter.- At most
4 * 104calls 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 < >();
Arrays.stream(words).forEach(word -> addWord(word));
}
public void addWord(String word) {
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) {
stream.addFirst(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];
}
}
}
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]
#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.add(w)
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))
}
StreamChecker.prototype.add = function(word) {
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
}
}
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]
#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)
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]
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _1032_StreamOfCharacters
{
private readonly Trie root;
private readonly List < char> stream;
public _1032_StreamOfCharacters(string[] words)
{
root = new Trie();
stream = new List < char>();
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)
{
stream.Add(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; }
}
}
}
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]