algoadvance

Given two strings first and second, consider occurrences in some text of the form “first second third”, where first and second are exactly the words first and second, respectively, and third is the word immediately following them.

Return a list of all the words third for each instance of “first second third” in the text.

Example:

text = "alice is a good girl she is a good student"
first = "a"
second = "good"

should return ["girl", "student"].

Clarifying Questions

  1. How do we handle punctuation or case sensitivity?
    • Assume that all words in the given text, first, and second are lowercase and without punctuation.
  2. What should be done if first and second appear at the end of the text without a subsequent third word?
    • If there is no following word after the occurrence of first second, skip this occurrence.
  3. Should we consider overlapping occurrences?
    • No, the phrase first second third is a distinct occurrence, and the search should continue after this occurrence.

Strategy

  1. Split the text into a list of words.
  2. Iterate through the list of words, checking for the pattern first second.
  3. If the pattern first second is found and a subsequent word exists, add the subsequent word to the result list.
  4. Return the list of subsequent words.

Code

def findOcurrences(text, first, second):
    words = text.split()
    result = []
    
    for i in range(len(words) - 2):
        if words[i] == first and words[i + 1] == second:
            result.append(words[i + 2])
    
    return result

# Example usage
text = "alice is a good girl she is a good student"
first = "a"
second = "good"
print(findOcurrences(text, first, second))  # Output: ["girl", "student"]

Time Complexity

Thus, the overall time complexity is O(n + m), which is essentially linear with respect to the length of the input text and the number of words in the list. Since m will usually be much smaller than n, the complexity can often be considered O(n).

Try our interview co-pilot at AlgoAdvance.com