Stream of characters

Array String Design Trie Data Stream

52.0% acceptance

Feb 22, 2026

1876

186

Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words. For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words. Implement the StreamChecker class: StreamChecker(String[] words) Initializes the object with the strings array words. boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

* impl StreamChecker {

 *     fn new(words: Vec<String>) -> Self {

 *     }

 *     fn query(&self, letter: char) -> bool {

 *     }
 * }
 */

/**
 * Your StreamChecker object will be instantiated and called as such:
 * let obj = StreamChecker::new(words);
 * let ret_1: bool = obj.query(letter);
 */

struct StreamChecker {
  trie: Vec<[i32; 26]>,
  is_end: Vec<bool>,
  stream: Vec<u8>,
  max_len: usize,
}

impl StreamChecker {
  fn new(words: Vec<String>) -> Self {
    let mut trie = vec![[- 1i32; 26]];
    let mut is_end = vec![false];
    let mut max_len = 0;
    for w in &words {
      max_len = max_len.max(w.len());
      let mut node = 0usize;
      for &b in w.as_bytes().iter().rev() {
        let c = (b - b'a') as usize;
        if trie[node][c] == -1 {
          trie[node][c] = trie.len() as i32;
          trie.push([-1i32; 26]);
          is_end.push(false);
        }
        node = trie[node][c] as usize;
      }
      is_end[node] = true;
    }
    StreamChecker { trie, is_end, stream: vec![], max_len }
  }

  fn query(&mut self, letter: char) -> bool {
    self.stream.push(letter as u8 - b'a');
    let mut node = 0usize;
    let start = if self.stream.len() > self.max_len { self.stream.len() - self.max_len } else { 0 };
    for &c in self.stream[start..].iter().rev() {
      let c = c as usize;
      if self.trie[node][c] == -1 { return false; }
      node = self.trie[node][c] as usize;
      if self.is_end[node] { return true; }
    }
    false
  }
}