Stream of Characters | LeetCode | Solution Explained

I explain the solution to the problem 1032. Stream of Characters in Python3 using Trie data structure. Answer explained in detail. Problem Link.

0. Stream of Characters: Problem Discussion

0.0. IO Format

• Given:
  • words
  • stream of characters (that forms a word): stream word
•  Goal:
  • return True or False if the stream word has a suffix in words
• Constraints:
  • 1 <= len(words) <= 2000
  • 1 <= len(words[i]) <= 2000
  • all characters in the entire problem are lowercase English letters

0.1. Examples

For ‘a’ we ask the question: is there any word that has a suffix of ‘a’ in the words? NO

For ‘b’ we ask the question: is there any word that has a suffix of ‘ab’ in the words? NO

For ‘c’ we ask the question: is there any word that has a suffix of ‘abc’ in the words? NO

For ‘d’ we ask the question: is there any word that has a suffix of ‘abcd’ in the words? YES, the suffix ‘cd’ of the word ‘abcd’ is present in words.

and so on.

1. Stream of Characters: Observations & Logic

1.0. Intuitions

I initially got thrown off by thinking about suffix. But I then immediately realized that a suffix of a word is just the prefix of the reversed word!

And now, since we are dealing with prefixes, what is a data structure that can efficiently help us mange these words?

Trie!

I have already created a detailed video on the intuitions, logic and the implementation of a trie over here: Implement Trie (Prefix Tree). Video link:

1.1. Dealing with stream word

Now that we can look at the words in reversed order, and create a “Suffix Trie” (implementation does not change!), we want to think about the stream word, which is given to us as an input character by character.

For the stream word at any point of time, we can again reverse it and travel the Trie we created! This will let us find the suffixes of the stream word.

In this case, we see how when we are at the character ‘d’ we already have the stream word as ‘abcd’, so we need to look at it in the reversed order, ‘dcba’ and the look at the suffixes:

• ‘d’ -> NO
• ‘dc’ -> YES; Present in the Suffix Trie (remember the word is reversed)
• ‘dcb’ -> NO
• ‘dcba’ -> NO

2. Stream of Characters: Implementation

2.0. Code

class TrieNode():
    def __init__(self, c, end=False):
        self.c = c
        self.child = {}
        self.end = end

class Trie():
    def __init__(self):
        self.root = TrieNode('#')
    
    def add_word(self, word):
        curr = self.root
        for c in word:
            if c not in curr.child:
                curr.child[c] = TrieNode(c)
            curr = curr.child[c]
        curr.end = True
    
    def does_word_exist(self, word):
        curr = self.root
        for c in word:
            if c not in curr.child: 
                return False
            curr = curr.child[c]
            if curr.end: return True
        
        return False

    # prints out the trie if you want, for debugging purposes!
    def print_trie(self):
        curr = self.root
        q = [curr]
        
        while q:
            temp = []
            for node in q:
                print(node.c, end="\t")

                for c in node.child:
                    temp.append(node.child[c])
            q = temp
            print("\n"+"="*80)

    
class StreamChecker:
    def __init__(self, words: List[str]):
        self.trie = Trie()
        for word in words:
            self.trie.add_word(word[::-1])
        self.word = ""
                    
    def query(self, letter: str) -> bool:
        self.word += letter
        return self.trie.does_word_exist(self.word[::-1])
        
        


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

2.1. Complexity Analysis

• Time: O(NM), N = len(words), M = len(words[i]) for creating the suffix trie
• Space: O(NM), to store the Trie.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.