Word Endings in a Letter Stream
Problem
A filter watches a chat message as it is typed, one letter at a time. It is given a list of banned words up front, and after each new letter it must report whether the text typed so far ends with any banned word. The stream can be very long, so each letter should cost time bounded by the length of the longest banned word, not by the length of the stream.
Examples
Input: words = ["cd", "f", "kl"], stream = "abcdefghijkl"
Output: [F, F, F, T, F, T, F, F, F, F, F, T]
Why: the text ends with "cd" after d, with "f" after f and with "kl" after lInput: words = ["ab", "bab"], stream = "bab"
Output: [F, F, T]
Why: after the last letter the text ends with both "ab" and "bab"Input: words = ["xyz"], stream = "xy"
Output: [F, F]
Why: edge case, the word is never completedHints
0 / 3
A normal prefix tree answers questions about how a string starts, but here every question is about how the text so far ends.
Store every banned word reversed. Then reading the recent letters from newest to oldest is a walk down the tree from the root, and a banned word ends at the newest letter exactly when that walk passes an end-of-word marker.
Keep only the last few letters, as many as the longest banned word, since older letters can never be part of a match. After each new letter, walk the reversed-word tree over those letters from newest to oldest and stop at the first marker or the first missing child.
Solution
A banned word ends at the newest letter exactly when that word, read backwards, is a prefix of the stream read backwards from the newest letter. So the banned words go into a prefix tree in reverse, and each query is a walk down that tree over the recent letters from newest to oldest, which succeeds at the first node that marks the end of a word and fails at the first missing child. Letters older than the longest word can never take part in a match, so a bounded buffer holds just those. Building the tree costs O(total characters), each letter then costs O(L) for the longest word length L, and the space is O(total characters plus L).
from collections import deque
class StreamFilter:
def __init__(self, words):
self.root, longest = {}, max(map(len, words))
for w in words:
node = self.root
for ch in reversed(w): # store every word backwards
node = node.setdefault(ch, {})
node["$"] = True
self.recent = deque(maxlen=longest) # older letters never matter
def feed(self, ch):
self.recent.append(ch)
node = self.root
for c in reversed(self.recent): # newest letter first
if c not in node:
return False
node = node[c]
if "$" in node:
return True
return False
f = StreamFilter(["cd", "f", "kl"])
print("".join("T" if f.feed(c) else "F" for c in "abcdefghijkl")) # -> FFFTFTFFFFFT
g = StreamFilter(["ab", "bab"])
print("".join("T" if g.feed(c) else "F" for c in "bab")) # -> FFT
h = StreamFilter(["xyz"])
print("".join("T" if h.feed(c) else "F" for c in "xy")) # -> FFStuck on the idea rather than the code? Word Search With a Trie covers it.