Stream of Characters
Hard · Tries · Array · String · Design · Trie · Data Stream
Problem
Design a checker that receives letters one at a time and reports whether the stream just finished spelling one of a set of words.
Implement StreamChecker:
- StreamChecker(words) builds the checker from a list of distinct words.
- query(letter) appends letter to the stream and returns true if some suffix of the stream received so far (ending at this letter) equals any of the words; otherwise false.
The tests replay a sequence of calls: ops names each call and vals holds its arguments; the output lists what each call returns (null for the constructor).
Examples
Input: ops = ["StreamChecker","query","query","query","query","query"], vals = [[["ok","book","e"]],["b"],["o"],["o"],["k"],["e"]] Output: [null,false,false,false,true,true]
After "book" both "book" and "ok" are suffixes; after "booke" the suffix "e" matches.
Input: ops = ["StreamChecker","query","query","query"], vals = [[["xyz"]],["x"],["y"],["z"]] Output: [null,false,false,true]
Only when the stream reads "xyz" does a word end.
Input: ops = ["StreamChecker","query","query","query","query","query","query","query","query","query","query","query","query"], vals = [[["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]
Matches at "d" (cd), "f" and "l" (kl); a word can reach back over letters received earlier.
Constraints
- 1 <= len(words) <= 2000
- 1 <= len(words[i]) <= 200
- words[i] and letter are lowercase English letters
- At most 4 · 10^4 calls to query
Approaches
- Baseline: test every word after every letter — time O(W) per query, space O(q)
Follow-up
Only the last L letters can matter, so a ring buffer of size L bounds memory however long the stream runs. To report every match rather than a yes or no, the Aho-Corasick automaton finds all words ending at each letter in time proportional to the matches; the use cases count the words ending at each letter and report the longest.
Related problems
Start free on Cariara · Coding problems · System design studio
