How hard is LeetCode 1032. Stream of Characters?

LeetCode 1032. Stream of Characters is rated Hard on LeetCode.

What is the time complexity of LeetCode 1032. Stream of Characters?

The Python solution on this page runs in O(total characters).

What is the space complexity of LeetCode 1032. Stream of Characters?

The Python solution on this page uses O(total characters) auxiliary space.

What topics does LeetCode 1032. Stream of Characters cover?

LeetCode 1032. Stream of Characters is tagged Design, Trie, Array, String and Data Stream on LeetCode.

Stream of Characters — LeetCode 1032 Python Solution

HardDesignTrieArrayStringData Stream

Problem: #1032
Pattern: Trie
Reading time: 8 min
Source: leetcode.com

The 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.

Example

Input: ["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
Output: [null, false, false, false, true, false, true, false, false, false, false, false, true]
Explanation: StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);

Python solution

Python

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, w: str):
        node = self
        for c in w[::-1]:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, w: List[str]) -> bool:
        node = self
        for c in w[::-1]:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return False
            node = node.children[idx]
            if node.is_end:
                return True
        return False


class StreamChecker:
    def __init__(self, words: List[str]):
        self.trie = Trie()
        self.cs = []
        self.limit = 201
        for w in words:
            self.trie.insert(w)

    def query(self, letter: str) -> bool:
        self.cs.append(letter)
        return self.trie.search(self.cs[-self.limit :])


# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)

Complexity

Measure	Complexity
Time	O(total characters)
Space	O(total characters) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 1032. Stream of Characters is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Trie.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1032. Stream of Characters?: LeetCode 1032. Stream of Characters is rated Hard on LeetCode.
What is the time complexity of LeetCode 1032. Stream of Characters?: The Python solution on this page runs in O(total characters).
What is the space complexity of LeetCode 1032. Stream of Characters?: The Python solution on this page uses O(total characters) auxiliary space.
What topics does LeetCode 1032. Stream of Characters cover?: LeetCode 1032. Stream of Characters is tagged Design, Trie, Array, String and Data Stream on LeetCode.