Stream of Characters

Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


**Input**
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["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]

**Explanation**
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // return False
streamChecker.query("b"); // return False
streamChecker.query("c"); // return False
streamChecker.query("d"); // return True, because 'cd' is in the wordlist
streamChecker.query("e"); // return False
streamChecker.query("f"); // return True, because 'f' is in the wordlist
streamChecker.query("g"); // return False
streamChecker.query("h"); // return False
streamChecker.query("i"); // return False
streamChecker.query("j"); // return False
streamChecker.query("k"); // return False
streamChecker.query("l"); // return True, because 'kl' is in the wordlist

Constraints

1 <= words.length <= 2000
1 <= words[i].length <= 200
words[i] consists of lowercase English letters.
letter is a lowercase English letter.
At most 4 * 10^4 calls will be made to query.

Solution

Method 1 - Reverse Trie for Suffix Matching

Intuition

To efficiently check if any suffix of the stream matches a word, we can build a trie of the reversed words. As each character arrives, we keep a buffer of the most recent characters (up to the length of the longest word) and traverse the trie from the newest character backward.

Approach

Build a trie with all words reversed.
For each query, append the new character to a buffer (deque or list).
For each query, traverse the trie from the newest character backward, checking for a word end.
If a word end is found, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


#include <vector>
#include <string>
#include <deque>
using namespace std;
struct TrieNode {
    TrieNode* children[26] = {};
    bool isWord = false;
};
class StreamChecker {
    TrieNode* root;
    deque<char> stream;
    int maxLen;
public:
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        maxLen = 0;
        for (auto& w : words) {
            TrieNode* node = root;
            maxLen = max(maxLen, (int)w.size());
            for (int i = w.size()-1; i >= 0; --i) {
                int idx = w[i] - 'a';
                if (!node->children[idx]) node->children[idx] = new TrieNode();
                node = node->children[idx];
            }
            node->isWord = true;
        }
    }
    bool query(char letter) {
        stream.push_front(letter);
        if (stream.size() > maxLen) stream.pop_back();
        TrieNode* node = root;
        for (char c : stream) {
            int idx = c - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
            if (node->isWord) return true;
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


type TrieNode struct {
    children [26]*TrieNode
    isWord bool
}
type StreamChecker struct {
    root *TrieNode
    stream []byte
    maxLen int
}
func Constructor(words []string) StreamChecker {
    root := &TrieNode{}
    maxLen := 0
    for _, w := range words {
        node := root
        if len(w) > maxLen { maxLen = len(w) }
        for i := len(w)-1; i >= 0; i-- {
            idx := w[i] - 'a'
            if node.children[idx] == nil {
                node.children[idx] = &TrieNode{}
            }
            node = node.children[idx]
        }
        node.isWord = true
    }
    return StreamChecker{root, []byte{}, maxLen}
}
func (sc *StreamChecker) Query(letter byte) bool {
    sc.stream = append([]byte{letter}, sc.stream...)
    if len(sc.stream) > sc.maxLen {
        sc.stream = sc.stream[:sc.maxLen]
    }
    node := sc.root
    for _, c := range sc.stream {
        idx := c - 'a'
        if node.children[idx] == nil { return false }
        node = node.children[idx]
        if node.isWord { return true }
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


import java.util.*;
class StreamChecker {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }
    TrieNode root = new TrieNode();
    Deque<Character> stream = new ArrayDeque<>();
    int maxLen = 0;
    public StreamChecker(String[] words) {
        for (String w : words) {
            TrieNode node = root;
            maxLen = Math.max(maxLen, w.length());
            for (int i = w.length()-1; i >= 0; i--) {
                int idx = w.charAt(i) - 'a';
                if (node.children[idx] == null) node.children[idx] = new TrieNode();
                node = node.children[idx];
            }
            node.isWord = true;
        }
    }
    public boolean query(char letter) {
        stream.addFirst(letter);
        if (stream.size() > maxLen) stream.removeLast();
        TrieNode node = root;
        for (char c : stream) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
            if (node.isWord) return true;
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class StreamChecker(words: Array<String>) {
    class TrieNode {
        val children = Array<TrieNode?>(26) { null }
        var isWord = false
    }
    private val root = TrieNode()
    private val stream = ArrayDeque<Char>()
    private var maxLen = 0
    init {
        for (w in words) {
            var node = root
            maxLen = maxOf(maxLen, w.length)
            for (i in w.length-1 downTo 0) {
                val idx = w[i] - 'a'
                if (node.children[idx] == null) node.children[idx] = TrieNode()
                node = node.children[idx]!!
            }
            node.isWord = true
        }
    }
    fun query(letter: Char): Boolean {
        stream.addFirst(letter)
        if (stream.size > maxLen) stream.removeLast()
        var node = root
        for (c in stream) {
            val idx = c - 'a'
            node = node.children[idx] ?: return false
            if (node.isWord) return true
        }
        return false
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


from collections import deque
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
class StreamChecker:
    def __init__(self, words: list[str]):
        self.root = TrieNode()
        self.max_len = 0
        for w in words:
            node = self.root
            self.max_len = max(self.max_len, len(w))
            for c in reversed(w):
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.is_word = True
        self.stream = deque()
    def query(self, letter: str) -> bool:
        self.stream.appendleft(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop()
        node = self.root
        for c in self.stream:
            if c not in node.children:
                return False
            node = node.children[c]
            if node.is_word:
                return True
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


use std::collections::VecDeque;
struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    is_word: bool,
}
impl TrieNode {
    fn new() -> Self {
        Self { children: Default::default(), is_word: false }
    }
}
pub struct StreamChecker {
    root: Box<TrieNode>,
    stream: VecDeque<char>,
    max_len: usize,
}
impl StreamChecker {
    pub fn new(words: Vec<String>) -> Self {
        let mut root = Box::new(TrieNode::new());
        let mut max_len = 0;
        for w in &words {
            let mut node = &mut root;
            max_len = max_len.max(w.len());
            for c in w.chars().rev() {
                let idx = (c as u8 - b'a') as usize;
                node = node.children[idx].get_or_insert_with(|| Box::new(TrieNode::new()));
            }
            node.is_word = true;
        }
        Self { root, stream: VecDeque::new(), max_len }
    }
    pub fn query(&mut self, letter: char) -> bool {
        self.stream.push_front(letter);
        if self.stream.len() > self.max_len {
            self.stream.pop_back();
        }
        let mut node = &self.root;
        for &c in &self.stream {
            let idx = (c as u8 - b'a') as usize;
            if let Some(child) = &node.children[idx] {
                node = child;
                if node.is_word { return true; }
            } else {
                return false;
            }
        }
        false
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class TrieNode {
    children: Map<string, TrieNode> = new Map();
    isWord = false;
}
class StreamChecker {
    private root = new TrieNode();
    private stream: string[] = [];
    private maxLen = 0;
    constructor(words: string[]) {
        for (const w of words) {
            let node = this.root;
            this.maxLen = Math.max(this.maxLen, w.length);
            for (let i = w.length - 1; i >= 0; i--) {
                const c = w[i];
                if (!node.children.has(c)) node.children.set(c, new TrieNode());
                node = node.children.get(c)!;
            }
            node.isWord = true;
        }
    }
    query(letter: string): boolean {
        this.stream.unshift(letter);
        if (this.stream.length > this.maxLen) this.stream.pop();
        let node = this.root;
        for (const c of this.stream) {
            if (!node.children.has(c)) return false;
            node = node.children.get(c)!;
            if (node.isWord) return true;
        }
        return false;
    }
}

Complexity

⏰ Time complexity: O(L) per query, where L is the max word length.
🧺 Space complexity: O(N*L) for N words of max length L.

Problem#

Examples#

Example 1#

Constraints#

Solution#

Method 1 - Reverse Trie for Suffix Matching#

Intuition#

Approach#

Code#

Complexity#