We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Stream of Characters

Difficulty: Hard

Problem Description

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.

Key Insights

  • The problem requires checking if any suffix of a stream matches any word from a given list.
  • A naive approach would be inefficient due to the potential length of the stream and the number of queries.
  • Using a Trie data structure allows efficient storage and lookup of words, enabling quick suffix checks.
  • The stream can be managed as a queue to maintain the order of incoming characters.

Space and Time Complexity

Time Complexity: O(N) per query in the worst case, where N is the length of the longest word in words. The insertion and lookup in the Trie will be O(K) where K is the average length of the words. Space Complexity: O(M) where M is the total number of characters in all words due to the Trie structure.

Solution

The solution uses a Trie data structure to store the words in reverse. When a new character is queried, it is prepended to the current stream. The algorithm then checks if any suffix of the current stream matches a word in the Trie. This allows efficient querying as the stream grows.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in reversed(word):  # insert the word in reverse
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search_suffix(self, stream):
        node = self.root
        for char in stream:
            if char in node.children:
                node = node.children[char]
                if node.is_end_of_word:
                    return True
            else:
                break
        return False

class StreamChecker:
    def __init__(self, words):
        self.trie = Trie()
        for word in words:
            self.trie.insert(word)
        self.stream = []

    def query(self, letter):
        self.stream.append(letter)
        return self.trie.search_suffix(self.stream)
← Back to All Questions