# 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 Stream of Characters: sample test case

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. Stream of Characters: dealing with 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('#')

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

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Disjoint Intervals | InterviewBit | Solution Explained

June 12, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.