Leetcode 1078. Occurrences After Bigram

Problem Explanation:

In this problem, let's consider occurrences in some given text phrases such as "first second third", where second comes immediately after first, and third comes immediately after second. We are supposed to return all the "third" words that follow a "first" word followed by a "second" word in that order.

For example, let's say we have a text string "alice is a good girl she is a good student", and our first and second words are "a" and "good", respectively. Then the answer should be ["girl", "student"] because these follow the words "a" and "good" in that order.

The approach to solving this problem is to split the text into individual words then iterate through these words to check if the current word is preceded by first and second words in that order. If this condition is met, the "third" word is appended to the answer list. We will be using the split function and iteration to solve this problem.

We continue with this until we have iterated through all the words, and then, we return the answer which contains all the "third" words.

Walkthrough:

Let's take an example, suppose we are given text = "we will we will rock you", first = "we", and second = "will".

we go through the text word by word:

  1. "we", "will":
    • The preceding words are not "we will", so continue.
  2. "will", "we":
    • The preceding words are "we will", add "we" in the answer list so answer = ["we"]
  3. "we", "will":
    • The preceding words are "will we", so continue.
  4. "will", "rock":
    • The preceding words are "we will", add "rock" in the answer list so answer = ["we", "rock"]
  5. "rock", "you":
    • The preceding words are "will rock", so continue.

Finally, the answer will be ["we", "rock"].

Python Solution:

1
2python
3class Solution:
4    def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
5        words = text.split()
6        res = []
7        for i in range(2, len(words)):
8            if words[i-2]==first and words[i-1]==second:
9                res.append(words[i])
10        return res

Java Solution:

1
2java
3class Solution {
4    public String[] findOcurrences(String text, String first, String second) {
5        String[] words = text.split(" ");
6        ArrayList<String> result = new ArrayList<String> ();
7        for (int i = 2; i < words.length; i++) {
8            if (words[i - 2].equals(first) && words[i - 1].equals(second)) {
9                result.add(words[i]);
10            }
11        }
12        return result.toArray(new String[0]);
13    }
14}

JavaScript Solution:

1
2javascript
3class Solution {
4    findOcurrences(text, first, second) {
5        const words = text.split(' ');
6        const res = [];
7        for (let i = 2; i < words.length; i++) {
8            if (words[i-2] === first && words[i-1] === second) {
9                res.push(words[i]);
10            }
11        }
12        return res;
13    }
14}

C++ Solution:

1
2cpp
3class Solution {
4public:
5    vector<string> findOcurrences(string text, string first, string second) {
6        vector<string> res;
7        stringstream ss(text);
8        string prev2, prev, word;
9        while (ss >> word) {
10            if (prev2 == first && prev == second)
11                res.push_back(word);
12            prev2 = prev;
13            prev = word;
14        }
15        return res;
16    }
17};

C# Solution:

1
2csharp
3public class Solution {
4    public string[] FindOcurrences(string text, string first, string second) {
5        string[] words = text.Split(' ');
6        List<string> result = new List<string>();
7        
8        for (int i = 2; i < words.Length; i++) {
9            if (words[i - 2] == first && words[i - 1] == second) {
10                result.Add(words[i]);
11            }
12        }
13        
14        return result.ToArray();
15    }
16}

These solutions are on the basis of the given "first" and "second" words as they represent the preceding words for the "third" word we are looking for. By iterating through the words in the text from the third word to the last, we always know the "first" and "second" words that precede the current word. If these words match the given words, we append the current word into our result list.

The Python and JavaScript solutions use lists to store the result, while the Java solution uses an ArrayList. The Python solution uses the built-in split() function for string separation, while JavaScript uses ' '.split(), and both have time complexity O(n), where n is the length of the array formed by splitting the text into words.

The Java solution uses the split() function with a same time complexity and converting the ArrayList to an array adds another O(n) operation, making the total time complexity still O(n).

Finally, these solutions can be implemented in an easier way if you know about Deque or Double Ended Queue which allows insertion and removal of elements from either end in O(1) time. Using deque we can always have the last two words and we can check if they are same as the given "first" and "second" words. If so, we add the third word to our result and in each iteration, we remove the oldest word from one end and add the new word in the other end, hence making the process more efficient.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫