algoadvance

Leetcode 1078. Occurrences After Bigram

Problem Statement

Given two strings first and second, consider all the occurrences of the first and second words appearing one after the other in the text. Return the list of words that appear immediately after the sequence of first and second.

Example 1:

Input: text = "alice is a good girl she is a good student", first = "a", second = "good"
Output: ["girl", "student"]

Example 2:

Input: text = "we will we will rock you", first = "we", second = "will"
Output: ["we", "rock"]

Constraints:

Clarifying Questions

  1. Q: Can we assume that text, first, and second are all lowercase? A: Yes.
  2. Q: Will the words in text only be composed of alphabetic characters? A: Yes.

Strategy

To solve the problem, we can follow these steps:

  1. Split the text into individual words using space as the delimiter.
  2. Iterate through the list of words and look for occurrences of the sequence of first followed by second.
  3. Whenever we find such a sequence, record the word immediately after the second word, if it exists.
  4. Return the list of words found in step 3.

Code

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

vector<string> findOcurrences(string text, string first, string second) {
    vector<string> result;
    vector<string> words;
    stringstream ss(text);
    string word;
    
    // Split the input text into words
    while (ss >> word) {
        words.push_back(word);
    }
    
    // Iterate through the words and find occurrences of first and second followed by another word
    for (int i = 0; i < words.size() - 2; ++i) {
        if (words[i] == first && words[i + 1] == second) {
            result.push_back(words[i + 2]);
        }
    }
    
    return result;
}

int main() {
    // Example 1
    string text1 = "alice is a good girl she is a good student";
    string first1 = "a";
    string second1 = "good";
    vector<string> result1 = findOcurrences(text1, first1, second1);
    for (const string &word : result1) {
        cout << word << " ";
    }
    cout << endl;

    // Example 2
    string text2 = "we will we will rock you";
    string first2 = "we";
    string second2 = "will";
    vector<string> result2 = findOcurrences(text2, first2, second2);
    for (const string &word : result2) {
        cout << word << " ";
    }
    cout << endl;

    return 0;
}

Time Complexity

This solution processes the input efficiently and meets the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI