Stream of Characters

1. Define the problem

You are given a list of words up front. Then letters arrive one at a time , forever. After each letter you must answer: do the last few letters received, taken together and ending with this newest one, spell one of the words? The catch is that the match must end at the newest letter , and you never know how far back to look. Checking every stored word after every letter would be far too slow. The trick is to store every word backwards in the trie. Then, when a letter arrives, walk the received letters from newest to oldest down that reversed trie. Hitting an end-of-word marker means a stored word finishes exactly at the newest letter. Because a class cannot be written down as plain data, this exercise uses the usual interview convention for design questions: a list of operation names and a matching list of argument lists come in, and the list of results comes out. The constructor takes the word list and produces null; each query takes one letter and produces true or false.

Constraints

1 ≤ words.length ≤ 2000
1 ≤ words_i.length ≤ 200
words_i and each queried letter are lowercase English letters
At most 4 × 10⁴ calls to query

Example

Input

operations = ["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query"], args = [[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"]]

Output[null, false, false, false, true, false, true, false, false]

Explanation After the letter d arrives the stream ends in "cd", which is one of the words, so the answer is true. After f arrives the stream ends in "f", also a word, so true again. Every other letter ends no word.

2. Know the words first

In plain terms

Stream: Data that arrives piece by piece over time rather than all at once. You must answer after each piece, before you know what comes next.
Suffix: The ending of a string. Checking "does a word end here?" means checking the suffixes of what has arrived so far.
Reversed trie: A trie built from words written backwards. Walking it from newest letter to oldest is the same as reading a word forwards.
Sliding window: Keeping only the most recent few items. No stored word is longer than the longest one, so older letters can be thrown away.

3. Visualize the solution

Answering each arriving letter with a trie of reversed words

a—

b—

c—

d—

e—

f—

Statusinit

The words cd, f and kl go into the trie backwards: dc, f and lk.

What happens in this step

words = ['cd', 'f', 'kl']
stored reversed: d->c, f, l->k
maxLength = 2, stream = []

Reversing means a walk from the newest letter backwards reads a word forwards.

Step 1 of 8

Steps to visualize

The row of cells is the stream of letters as they arrive, one cell per letter.
The value is the answer given for that letter: "yes" if a stored word ends there, "no" if not, and "—" if the letter has not arrived yet.
The frame marks the letter that just arrived, which is where every check must end.
Each check walks backwards from the framed letter down the reversed trie, and stops the moment the path runs out.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Answering each arriving letter with a trie of reversed words

a—

b—

c—

d—

e—

f—

Statusinit

The words cd, f and kl go into the trie backwards: dc, f and lk.

What happens in this step

words = ['cd', 'f', 'kl']
stored reversed: d->c, f, l->k
maxLength = 2, stream = []

Reversing means a walk from the newest letter backwards reads a word forwards.

Step 1 of 8

5. Solution

Solution

solution.tsTypeScript

function runStreamCheckerOperations(operations, args) {
  class TrieNode {
    constructor() {
      this.children = {};
      this.isEnd = false;
    }
  }

  class StreamChecker {
    constructor(words) {
      this.root = new TrieNode();
      this.stream = [];
      this.maxLength = 0;

      for (const word of words) {
        this.maxLength = Math.max(this.maxLength, word.length);

        let node = this.root;
        for (let i = word.length - 1; i >= 0; i--) {
          const ch = word[i];
          if (!node.children[ch]) {
            node.children[ch] = new TrieNode();
          }
          node = node.children[ch];
        }
        node.isEnd = true;
      }
    }

    query(letter) {
      this.stream.push(letter);
      if (this.stream.length > this.maxLength) {
        this.stream.shift();
      }

      let node = this.root;
      for (let i = this.stream.length - 1; i >= 0; i--) {
        node = node.children[this.stream[i]];
        if (!node) {
          return false;
        }
        if (node.isEnd) {
          return true;
        }
      }

      return false;
    }
  }

  const results = [];
  let checker = null;

  for (let i = 0; i < operations.length; i++) {
    if (operations[i] === 'StreamChecker') {
      checker = new StreamChecker(args[i][0]);
      results.push(null);
    } else {
      results.push(checker.query(args[i][0]));
    }
  }

  return results;
}

Time: O(total letters in words) to build, O(maxLength) per query
Space: O(total letters in words)

6. Test cases

Test cases

Input	Expected	Covers
`operations = ["StreamChecker", "query" x 8], args = [[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"]]`	`[null, false, false, false, true, false, true, false, false]`	example from the docstring
`words = ["a"], then queries a, b, a`	`[null, true, false, true]`	a one-letter word matches every time that letter arrives
`words = [], then queries a, b`	`[null, false, false]`	an empty word list can never match anything
`words = ["abcd"], then queries a, b, c, d`	`[null, false, false, false, true]`	a longer word only matches once its last letter arrives
`words = ["ab", "b"], then queries a, b`	`[null, false, true]`	two words could end at the same letter, one match is enough
`words = ["aa"], then queries a, a, a`	`[null, false, true, true]`	the same word matching again on overlapping letters

Stream of Characters