Advanced Data Structures: Implementing Tries in C++ and Java/

...

/

Suffix Stream

Suffix Stream

Solve a hard-level problem of identifying word suffixes from a stream of characters.

We'll cover the following...

Problem statement

Given an array of strings called words and a stream of letters S, check if a suffix of these letters is present as a string in the input array of words. If a non-empty suffix is present as a string, then return true; else, return false.

Example

Sample input

words: ["efg", "pqr"]
S: ['e','p','q','r']

Sample output

[false,false,false,true]

Explanation

One by one, the stream added the four characters 'e', 'p', 'q', and 'r'.
1. No suffix of the character "e" matches any word from the array.
2. No suffix of the characters "ep" matches any word from the array.
3. No suffix of the characters "epq" matches any word from the array.
4. The suffix "pqr" of the characters "epqr" matches "pqr" from the words array.

Try it yourself

Please try to solve the problem yourself before reading the solution.

#include <iostream>

#include <vector>

using namespace std;



vector<bool> suffixStreamCheck(vector<string> words, vector<char> queryStream){

    // your code goes here

    vector<bool> result;

    return result;   

}
Solve suffix stream in C++

Intuition

Hashset-based approach

One way is to insert all the words into the hashset and then check if any suffix of the query stream exists in the hashset or not. For efficiency, we reverse the words before inserting them into the hashset. While querying, we form reverse suffix strings beginning from the last character in the query stream and going to the first character. It's important to note that the stream input can be very large in size. We can optimize by only checking for suffix strings that are less than or equal to the length of the longest string in words.

Press + to interact
SuffixStream {
    // initialize a set 
    Set S
    // initialize a queryStream
    String queryStream 
    integer maxWordLength = 0;
    insertWords(words){
        for w in words {
            // reverse word and insert into set
            reverse(w)
            S.insert(w)
            // maintain the length of the longest word
            // in a variable maxWordLength
            maxWordLength = max(size(w), maxWordLength)
        }
    }
    
    query(ch) {
        queryStream += ch;
        String suffix
        // keep adding stream characters to generate suffix strings
        for(int i = size(queryStream)-1; i >= max(0, size(queryStream)-maxWordLength); i--) {
            suffix += queryStream[i];
            // check if suffix exists in set
            if(S.find(suffix)) 
              return true;
        }
        return false;
    }
}

The illustration below depicts the hashset-based approach.

Time complexity

Let's consider the number of words in the list as NN and the maximum size of the word as WW. The time complexity of reversing the words and inserting them into a hashset is O(NW)O(NW). While querying, we check for W ...

Access this course and 1400+ top-rated courses and projects.