Abstract / Summary

Check if a sequence of characters is a current prefix of the stream efficiently after each insertion.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 52% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Data Stream
• Design
• String
• Trie

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The StreamChecker class provides an interface for incremental character queries against a predefined dictionary of words. It builds an internal representation that groups words by their final character, then maintains a growing character stream. Each query appends a new character to the stream and determines whether any stored word appears as a suffix of the current stream.

Initialization

The constructor receives a list of words and prepares a lookup structure that enables fast access to candidate words for each incoming character.

def __init__(self, words: List[str]):
    self.abc  = defaultdict(set) # dict based on last letter
    for w in words:
        self.abc[w[-1]].add(w)

    self.stream = ""

• The defaultdict(set) called abc maps a character (the last letter of a word) to a set containing all words that end with that character.
• The loop iterates over every word, extracts its last character with w[-1], and inserts the word into the appropriate set.
• An empty string self.stream is created to accumulate the characters supplied by successive query calls.

Query Processing

The query method updates the internal stream and checks for a matching suffix.

def query(self, letter: str) -> bool:
    self.stream += letter
    for w in self.abc[letter]:
        if self.stream.endswith(w):
            return True
    return False

• The incoming letter is concatenated to self.stream.
• The method retrieves the set of candidate words whose last character equals the newly added letter via self.abc[letter].
• For each candidate word w, the built-in endswith function tests whether the current stream terminates with w.
• The first successful match causes an immediate True return; otherwise the method returns False after exhausting the candidate set.

Edge Cases Handled

When the input word list contains single-character entries, those words are stored under the same key as their sole character. The query method will correctly identify a match as soon as the corresponding character is streamed because self.stream.endswith(w) evaluates to True for a one-character suffix.

If the word list is empty, self.abc remains an empty mapping. Any call to query will retrieve an empty set for the supplied letter, causing the loop to skip entirely and return False. This gracefully handles the absence of any searchable words.

Words that share the same final character are grouped together in a single set. The iteration over self.abc[letter] therefore examines all possible matches for that character, ensuring that overlapping suffixes (e.g., “a” and “ba”) are both considered.

Performance Optimizations

The primary optimization is the partitioning of the word dictionary by last character. By limiting the suffix check to only those words that could possibly end with the newly added character, the algorithm avoids unnecessary comparisons against unrelated words. This reduces the average number of endswith evaluations per query.

Storing the groups in a set provides constant-time membership checks for the grouping operation itself, and iteration over a set is generally faster than iterating over a list when duplicate entries are not needed.

The use of Python’s native str.endswith leverages a highly optimized C implementation for suffix comparison, which is faster than a manual character-by-character loop.

Overall, the design balances memory usage (a dictionary of sets) with query-time efficiency by narrowing the search space to the minimal relevant subset of words for each streamed character.

Imagine a magical library book that learns new words as letters arrive one by one. The code starts by organizing a list of secret words, looking specifically at the very last letter of each word to group them together. This way, the code keeps track of which words belong to which letter.

When a new letter arrives, the code adds it to a growing string that keeps a history of everything seen so far. After adding the letter, the code looks at the special group for that letter to see if any of those secret words are hiding at the very end of the growing string. If a word from the group is found at the end of the history, the code recognizes it.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	Garvit244		Python
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	XiaotaoGuo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
Garvit244	Python
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
XiaotaoGuo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality