Leetcode – Occurrences After Bigram Solution

Spread the love

Text processing is a foundational area of computer science, forming the bedrock of areas like natural language processing, information retrieval, and machine learning. The “Occurrences After Bigram” problem on Leetcode taps into this domain, requiring us to search for patterns in strings. This article will provide an in-depth look at this problem, from understanding its intricacies to diving into various solution methodologies, all while grounding our explorations in Python.

Table of Contents:

  1. Problem Statement
  2. Understanding the Problem
  3. Approaches to Solution
  4. Python Implementations
  5. Analysis of Time and Space Complexity
  6. Wrapping Up

1. Problem Statement:

Given words first and second, consider a bigram (sequence of two words) of text. For each such sequence, if first and second are the two words in the sequence, add the third word to the answer.

Return an array of words formed by the third word in each bigram sequence.

Example:

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

2. Understanding the Problem:

At the core, the problem is asking us to recognize patterns of three words in a given text. Specifically, when we see the words first followed by second, we need to capture the third word.

3. Approaches to Solution:

  1. Iterative Approach: Tokenize the text into words and iterate through the list of words, checking each triplet.
  2. Sliding Window: Use a window of size three and slide it over the text to detect the desired patterns.

4. Python Implementations:

1. Iterative Approach:

This method requires us to first split the text into individual words and then iterate through the list, checking each consecutive triplet.

def findOcurrences_iterative(text, first, second):
    words = text.split()
    result = []

    for i in range(2, len(words)):
        if words[i-2] == first and words[i-1] == second:
            result.append(words[i])

    return result

2. Sliding Window Approach:

This method requires us to maintain a window of three words and slide it over the list of words. If the first two words in the window match the given first and second, the third word is added to our result.

def findOcurrences_window(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

5. Analysis of Time and Space Complexity:

  • Iterative Approach:
    • Time Complexity: O(n), where n is the number of words in text. We iterate through the list of words once.
    • Space Complexity: O(n), due to the space required to store the split words and the resulting list.
  • Sliding Window Approach:
    • Time Complexity: O(n), as we slide the window across the list of words once.
    • Space Complexity: O(n), for the same reasons as the iterative approach.

6. Wrapping Up:

The “Occurrences After Bigram” problem showcases the importance of recognizing patterns in text and the versatility of Python in handling strings and lists. While there are multiple ways to approach the problem, the iterative and sliding window methods present efficient and intuitive solutions.

Leave a Reply