We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Occurrences After Bigram

Number: 1156

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a string text and two words first and second, find all occurrences in text of the pattern "first second third" and return an array containing each third word that comes immediately after every occurrence of "first second".

Key Insights

  • Split the text using space as the delimiter.
  • Traverse the list of words and check for consecutive words matching first and second.
  • When the pattern is found, capture the word that immediately follows.
  • Ensure not to go out of bounds when checking the next word.
  • The overall approach runs in linear time relative to the number of words.

Space and Time Complexity

Time Complexity: O(n) where n is the number of words in text.
Space Complexity: O(n) due to the list of words and the output list in the worst-case scenario.

Solution

The solution involves splitting the text into an array of words, then iterating through the array to identify every occurrence where a word matching first is immediately followed by a word matching second. For each valid occurrence, capture the subsequent word (if it exists) and add it to the result list. This approach is straightforward and efficient since it processes the text in one pass.

Code Solutions

# Python solution for Occurrences After Bigram
def findOcurrences(text: str, first: str, second: str) -> list:
    # Split the text into a list of words
    words = text.split(" ")
    # Initialize the result list
    result = []
    # Iterate through the words list, stopping two words before end
    for i in range(len(words) - 2):
        # Check if the current word and the next word match first and second respectively
        if words[i] == first and words[i+1] == second:
            # Append the third word to the result list
            result.append(words[i+2])
    return result

# Example usage:
print(findOcurrences("alice is a good girl she is a good student", "a", "good"))
← Back to All Questions