1078. Occurrences After Bigram
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 65.0%
Problem Breakdown
The problem requires us to find all words that come immediately after a specific bigram (a pair of consecutive words) in a given text. The inputs are:
text: A string containing space-separated lowercase English letters.first: A single word that is part of the bigram.second: A single word that is part of the bigram.
The output should be an array of words that follow the specified bigram in the text. The constraints are:
- The length of
textis between 1 and 1000 characters. - Each word in
textconsists of lowercase English letters. - The lengths of
firstandsecondare between 1 and 10 characters.
Edge cases include:
- The text might contain multiple occurrences of the bigram.
- The text might not contain the bigram at all.
- The text could be very short or very long.
Intuition
A brute-force approach would involve splitting the text into words and then iterating through the list to check for the bigram. This approach is straightforward but has a time complexity of O(n^2) due to the nested loops (one for iterating through the words and another for checking the bigram).
The key insight is to use a single pass through the text by splitting it into words and then checking each pair of consecutive words to see if they match the bigram. If they do, we add the next word to our result list.
Approach
- Split the input
textinto a list of words. - Initialize an empty list
resultto store the words that follow the bigram. - Iterate through the list of words from index 0 to n-2 (where n is the number of words).
- For each word at index i, check if it and the next word (at index i+1) form the bigram (
firstandsecond). - If they do, add the word following the bigram (at index i+2) to the
resultlist. - Return the
resultlist.
Complexity Analysis
- Time Complexity: O(n), where n is the number of words in the text. We make a single pass through the list of words.
- Space Complexity: O(n), where n is the number of words in the text. This is due to the storage required for the list of words and the result list.
Solution
def findOcurrences(text: str, first: str, second: str) -> List[str]:
# Split the text into a list of words
words = text.split()
# Initialize an empty list to store the results
result = []
# Iterate through the words up to the third last word
for i in range(len(words) - 2):
# Check if the current and next word form the bigram
if words[i] == first and words[i + 1] == second:
# Add the word following the bigram to the result list
result.append(words[i + 2])
return result
Edge Cases Handled
- No occurrences of the bigram: The function will return an empty list.
- Multiple occurrences of the bigram: All occurrences are captured and added to the result list.
- Short text with fewer than two words: The function handles this gracefully by returning an empty list since no bigram can exist.