LeetCode 1032: Stream of Characters (Reversed Trie + Suffix Query)
LeetCode 1032TrieStreamToday we solve LeetCode 1032 - Stream of Characters.
Source: https://leetcode.com/problems/stream-of-characters/
English
Problem Summary
Design a data structure that receives characters one by one. After each query, return whether any suffix of the stream matches one word in a given dictionary.
Key Insight
Suffix checking is easier if we reverse dictionary words and scan the stream backward. Build a trie on reversed words, append each incoming letter to a buffer, and walk from buffer end toward front. If we hit a terminal trie node, answer is true.
Algorithm
- Build trie with each word inserted in reversed order.
- Keep all queried letters in a dynamic buffer.
- On each query, traverse trie from newest letter backward.
- If path breaks, return false; if terminal node appears, return true.
Complexity Analysis
Let L be max word length.
Each query checks at most L chars.
Time per query: O(L).
Build: O(total word length).
Space: O(total word length + stream).
Common Pitfalls
- Building trie in forward order, which makes suffix matching awkward.
- Forgetting early return when terminal node is reached.
- Scanning entire stream every time instead of stopping at missing edge.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class StreamChecker {
private static class Node {
Node[] next = new Node[26];
boolean end;
}
private final Node root = new Node();
private final StringBuilder stream = new StringBuilder();
public StreamChecker(String[] words) {
for (String w : words) {
Node cur = root;
for (int i = w.length() - 1; i >= 0; i--) {
int idx = w.charAt(i) - 'a';
if (cur.next[idx] == null) cur.next[idx] = new Node();
cur = cur.next[idx];
}
cur.end = true;
}
}
public boolean query(char letter) {
stream.append(letter);
Node cur = root;
for (int i = stream.length() - 1; i >= 0; i--) {
int idx = stream.charAt(i) - 'a';
if (cur.next[idx] == null) return false;
cur = cur.next[idx];
if (cur.end) return true;
}
return false;
}
}type Node struct {
next [26]*Node
end bool
}
type StreamChecker struct {
root *Node
stream []byte
}
func Constructor(words []string) StreamChecker {
root := &Node{}
for _, w := range words {
cur := root
for i := len(w) - 1; i >= 0; i-- {
idx := int(w[i] - 'a')
if cur.next[idx] == nil {
cur.next[idx] = &Node{}
}
cur = cur.next[idx]
}
cur.end = true
}
return StreamChecker{root: root}
}
func (this *StreamChecker) Query(letter byte) bool {
this.stream = append(this.stream, letter)
cur := this.root
for i := len(this.stream) - 1; i >= 0; i-- {
idx := int(this.stream[i] - 'a')
if cur.next[idx] == nil {
return false
}
cur = cur.next[idx]
if cur.end {
return true
}
}
return false
}class StreamChecker {
private:
struct Node {
Node* next[26]{};
bool end = false;
};
Node* root;
string stream;
public:
StreamChecker(vector<string>& words) {
root = new Node();
for (const string& w : words) {
Node* cur = root;
for (int i = (int)w.size() - 1; i >= 0; --i) {
int idx = w[i] - 'a';
if (!cur->next[idx]) cur->next[idx] = new Node();
cur = cur->next[idx];
}
cur->end = true;
}
}
bool query(char letter) {
stream.push_back(letter);
Node* cur = root;
for (int i = (int)stream.size() - 1; i >= 0; --i) {
int idx = stream[i] - 'a';
if (!cur->next[idx]) return false;
cur = cur->next[idx];
if (cur->end) return true;
}
return false;
}
};class Node:
__slots__ = ("next", "end")
def __init__(self):
self.next = {}
self.end = False
class StreamChecker:
def __init__(self, words: List[str]):
self.root = Node()
self.stream = []
for w in words:
cur = self.root
for ch in reversed(w):
if ch not in cur.next:
cur.next[ch] = Node()
cur = cur.next[ch]
cur.end = True
def query(self, letter: str) -> bool:
self.stream.append(letter)
cur = self.root
for i in range(len(self.stream) - 1, -1, -1):
ch = self.stream[i]
if ch not in cur.next:
return False
cur = cur.next[ch]
if cur.end:
return True
return Falseclass Node {
constructor() {
this.next = new Array(26).fill(null);
this.end = false;
}
}
var StreamChecker = function(words) {
this.root = new Node();
this.stream = [];
for (const w of words) {
let cur = this.root;
for (let i = w.length - 1; i >= 0; i--) {
const idx = w.charCodeAt(i) - 97;
if (!cur.next[idx]) cur.next[idx] = new Node();
cur = cur.next[idx];
}
cur.end = true;
}
};
StreamChecker.prototype.query = function(letter) {
this.stream.push(letter);
let cur = this.root;
for (let i = this.stream.length - 1; i >= 0; i--) {
const idx = this.stream[i].charCodeAt(0) - 97;
if (!cur.next[idx]) return false;
cur = cur.next[idx];
if (cur.end) return true;
}
return false;
};中文
题目概述
设计一个数据结构，每次输入一个字符。每次查询时判断当前字符流的某个后缀是否等于词典中的任意单词。
核心思路
后缀匹配可以转成“反向前缀匹配”。把所有单词倒序插入 Trie，然后每次从字符流末尾往前走 Trie。只要走到终止节点，就说明存在匹配后缀。
算法步骤
- 将每个单词按倒序插入 Trie。
- 用缓冲区保存已查询字符流。
- 每次 query 从最新字符向前遍历 Trie。
- 遇到空边直接返回 false；遇到单词结尾返回 true。
复杂度分析
设 L 为词典中最长单词长度。
每次查询最多检查 L 个字符。
单次查询时间：O(L)。
建树：O(单词总长度)。
空间：O(单词总长度 + 字符流)。
常见陷阱
- Trie 没有倒序建，导致后缀查询不自然。
- 命中终止节点后没有立即返回。
- 每次都无脑扫完整个流，没有在失配时提前停止。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class StreamChecker {
private static class Node {
Node[] next = new Node[26];
boolean end;
}
private final Node root = new Node();
private final StringBuilder stream = new StringBuilder();
public StreamChecker(String[] words) {
for (String w : words) {
Node cur = root;
for (int i = w.length() - 1; i >= 0; i--) {
int idx = w.charAt(i) - 'a';
if (cur.next[idx] == null) cur.next[idx] = new Node();
cur = cur.next[idx];
}
cur.end = true;
}
}
public boolean query(char letter) {
stream.append(letter);
Node cur = root;
for (int i = stream.length() - 1; i >= 0; i--) {
int idx = stream.charAt(i) - 'a';
if (cur.next[idx] == null) return false;
cur = cur.next[idx];
if (cur.end) return true;
}
return false;
}
}type Node struct {
next [26]*Node
end bool
}
type StreamChecker struct {
root *Node
stream []byte
}
func Constructor(words []string) StreamChecker {
root := &Node{}
for _, w := range words {
cur := root
for i := len(w) - 1; i >= 0; i-- {
idx := int(w[i] - 'a')
if cur.next[idx] == nil {
cur.next[idx] = &Node{}
}
cur = cur.next[idx]
}
cur.end = true
}
return StreamChecker{root: root}
}
func (this *StreamChecker) Query(letter byte) bool {
this.stream = append(this.stream, letter)
cur := this.root
for i := len(this.stream) - 1; i >= 0; i-- {
idx := int(this.stream[i] - 'a')
if cur.next[idx] == nil {
return false
}
cur = cur.next[idx]
if cur.end {
return true
}
}
return false
}class StreamChecker {
private:
struct Node {
Node* next[26]{};
bool end = false;
};
Node* root;
string stream;
public:
StreamChecker(vector<string>& words) {
root = new Node();
for (const string& w : words) {
Node* cur = root;
for (int i = (int)w.size() - 1; i >= 0; --i) {
int idx = w[i] - 'a';
if (!cur->next[idx]) cur->next[idx] = new Node();
cur = cur->next[idx];
}
cur->end = true;
}
}
bool query(char letter) {
stream.push_back(letter);
Node* cur = root;
for (int i = (int)stream.size() - 1; i >= 0; --i) {
int idx = stream[i] - 'a';
if (!cur->next[idx]) return false;
cur = cur->next[idx];
if (cur->end) return true;
}
return false;
}
};class Node:
__slots__ = ("next", "end")
def __init__(self):
self.next = {}
self.end = False
class StreamChecker:
def __init__(self, words: List[str]):
self.root = Node()
self.stream = []
for w in words:
cur = self.root
for ch in reversed(w):
if ch not in cur.next:
cur.next[ch] = Node()
cur = cur.next[ch]
cur.end = True
def query(self, letter: str) -> bool:
self.stream.append(letter)
cur = self.root
for i in range(len(self.stream) - 1, -1, -1):
ch = self.stream[i]
if ch not in cur.next:
return False
cur = cur.next[ch]
if cur.end:
return True
return Falseclass Node {
constructor() {
this.next = new Array(26).fill(null);
this.end = false;
}
}
var StreamChecker = function(words) {
this.root = new Node();
this.stream = [];
for (const w of words) {
let cur = this.root;
for (let i = w.length - 1; i >= 0; i--) {
const idx = w.charCodeAt(i) - 97;
if (!cur.next[idx]) cur.next[idx] = new Node();
cur = cur.next[idx];
}
cur.end = true;
}
};
StreamChecker.prototype.query = function(letter) {
this.stream.push(letter);
let cur = this.root;
for (let i = this.stream.length - 1; i >= 0; i--) {
const idx = this.stream[i].charCodeAt(0) - 97;
if (!cur.next[idx]) return false;
cur = cur.next[idx];
if (cur.end) return true;
}
return false;
};
Comments