Stream of Characters Problem


Description

LeetCode Problem 1032. Implement the StreamChecker class as follows.

  • StreamChecker(words): Constructor, initialize the data structure with the given words.
  • query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

Words and queries will only consist of lowercase English letters.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // initialize the dictionary.
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


Solution

Trie and Queue Approach

We can use the trie data structure to solve this problem. How to build a trie structure and store the stream can be found in the Implement Trie Problem post.

For all the queries, we use a queue to store the TrieNodes that are still valid for the current querying letter.

Every time we get a query, we push the root TrieNode to the queue. Then for every TrieNode in the queue, we check whether the querying letter exists in the array of next TrieNodes. If so, we point to the next TrieNode and push that TrieNode back to the queue; otherwise, we will remove the TrieNode from the queue. If the is_end tag of any of the TrieNodes in the queue is true, it means we find a word and we can return true.

Here is a walk-through of the approach. The trie is [“cd”,”f”,”kl”], and the queries are (‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’, ‘l’).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Trie
c   f*  k
|       |
d*      l*

Queries:
| query | queue 
    a   |   -   <-- root->arr['a'-'a'] is NULL, queue is empty, return false
    b   |   -   <-- root->arr['b'-'a'] is NULL, queue is empty, return false
    c   |   c   <-- root->arr['c'-'a'] is not NULL, push root->arr['c'-'a'] to queue, return false
    d   |   d   <-- root->arr['c'-'a']->arr['d'-'a'] is not NULL, root->arr['d'-'a'] is NULL, push root->arr['c'-'a']->arr['d'-'a'] to queue, is_end is true, return true
    e   |   -   <-- root->arr['c'-'a']->arr['d'-'a']->arr['e'-'a'] is NULL, root->arr['e'-'a'] is NULL, queue is empty, return false
    f   |   f   <-- root->arr['f'-'a'] is not NULL, push root->arr['f'-'a'] to queue, is_end is true, return true
    g   |   -   <-- root->arr['f'-'a']->arr['g'-'a'] is NULL, root->arr['g'-'a'] is NULL, queue is empty, return false
    h   |   -   <-- root->arr['h'-'a'] is NULL, queue is empty, return false
    i   |   -   <-- root->arr['i'-'a'] is NULL, queue is empty, return false
    j   |   -   <-- root->arr['j'-'a'] is NULL, queue is empty, return false
    k   |   k   <-- root->arr['k'-'a'] is not NULL, push root->arr['k'-'a'] to queue, return false
    l   |   l   <-- root->arr['k'-'a']->['l'-'a'] is not NULL, root->arr['l'-'a'] is NULL, push root->arr['k'-'a']->arr['l'-'a'] to queue, is_end is true, return true


Sample C++ Code

This is a C++ implementation of the trie and queue approach.

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

class StreamChecker {
public:
    struct TrieNode {
        TrieNode* arr[26];
        bool is_end;
        TrieNode() {
            for (int i = 0; i < 26; i ++) arr[i] = NULL;
            is_end = false;
        }
    };
    
    TrieNode* root;
    queue<TrieNode*> q;
    
    void insert(TrieNode* root, string key) {
        TrieNode* curr = root;
        for (int i = 0; i < key.size(); i ++) {
            int idx = key[i] - 'a';
            if (curr->arr[idx] == NULL)
                curr->arr[idx] = new TrieNode();
            curr = curr->arr[idx];
        }
        curr->is_end = true;
    }
    
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        for (int i = 0; i < words.size(); i ++)
            insert(root, words[i]);
    }
    
    bool query(char letter) {
        q.push(root);
        int len = q.size();
        int idx = letter - 'a';
        TrieNode* curr;
        bool flag = false;
        for (int i = 0; i < len; i ++) {
            curr = q.front();
            q.pop();
            if (curr->arr[idx] != NULL) {
                if (curr->arr[idx]->is_end) {
                    flag = true;
                } 
                q.push(curr->arr[idx]);
            }    
        }
        return flag;
    }
};

int main() {
    vector<string> words = {"cd", "f", "kl"};
    StreamChecker* obj = new StreamChecker(words);
    cout << obj->query('a') << endl;
    cout << obj->query('b') << endl;
    cout << obj->query('c') << endl;
    cout << obj->query('d') << endl;
    cout << obj->query('e') << endl;
    cout << obj->query('f') << endl;
    cout << obj->query('g') << endl;
    cout << obj->query('h') << endl;
    cout << obj->query('i') << endl;
    cout << obj->query('j') << endl;
    cout << obj->query('k') << endl;
    cout << obj->query('l') << endl;
    return 0;
}




Related Posts

Stream of Characters Problem

LeetCode 1032. Implement the StreamChecker class as follows. Constructor, initialize...

Maximum XOR of Two Numbers in an Array Problem

LeetCode 421. Given an integer array nums, return the maximum...

Implement Trie (Prefix Tree) Problem

LeetCode 208. Implement a Trie with insert, search, and startsWith...

Camelcase Matching Problem

LeetCode 1023. A query word matches a given pattern if...

Word Search II Problem

LeetCode 212. Given an m x n board of characters...

Replace Words Problem

LeetCode 648. Given a dictionary consisting of many roots, and...