In this guide, you will get 1032. Stream of Characters LeetCode Solution with the best time and space complexity. The solution to Stream of Characters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Complexity Analysis
Time Complexity: O(\max(|\texttt{words[i]}|))
Space Complexity: O(\max(|\texttt{words[i]}|))
1032. Stream of Characters LeetCode Solution in C++
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
bool isWord = false;
TrieNode() : children(26) {}
};
class StreamChecker {
public:
StreamChecker(vector<string>& words) {
for (const string& word : words)
insert(word);
}
bool query(char letter) {
letters += letter;
shared_ptr<TrieNode> node = root;
for (int i = letters.length() - 1; i >= 0; --i) {
const int index = letters[i] - 'a';
if (node->children[index] == nullptr)
return false;
node = node->children[index];
if (node->isWord)
return true;
}
return false;
}
private:
shared_ptr<TrieNode> root = make_shared<TrieNode>();
string letters;
void insert(const string& word) {
shared_ptr<TrieNode> node = root;
for (int i = word.length() - 1; i >= 0; --i) {
const int index = word[i] - 'a';
if (node->children[index] == nullptr)
node->children[index] = make_shared<TrieNode>();
node = node->children[index];
}
node->isWord = true;
}
}; /* code provided by PROGIEZ */
1032. Stream of Characters LeetCode Solution in Java
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public boolean isWord = false;
}
class StreamChecker {
public StreamChecker(String[] words) {
for (final String word : words)
insert(word);
}
public boolean query(char letter) {
letters.append(letter);
TrieNode node = root;
for (int i = letters.length() - 1; i >= 0; --i) {
final int index = letters.charAt(i) - 'a';
if (node.children[index] == null)
return false;
node = node.children[index];
if (node.isWord)
return true;
}
return false;
}
private TrieNode root = new TrieNode();
private StringBuilder letters = new StringBuilder();
private void insert(final String word) {
TrieNode node = root;
for (int i = word.length() - 1; i >= 0; --i) {
final int index = word.charAt(i) - 'a';
if (node.children[index] == null)
node.children[index] = new TrieNode();
node = node.children[index];
}
node.isWord = true;
}
} // code provided by PROGIEZ
1032. Stream of Characters LeetCode Solution in Python
from dataclasses import dataclass
@dataclass
class TrieNode:
children: dict[str, TrieNode]
isWord: bool
class StreamChecker:
def __init__(self, words: list[str]):
self.root = TrieNode()
self.letters = []
for word in words:
self._insert(word)
def query(self, letter: str) -> bool:
self.letters.append(letter)
node = self.root
for c in reversed(self.letters):
if c not in node.children:
return False
node = node.children[c]
if node.isWord:
return True
return False
def _insert(self, word: str) -> None:
node = self.root
for c in reversed(word):
node = node.children.setdefault(c, TrieNode())
node.isWord = True # code by PROGIEZ
