[Leetcode 1078] Occurrences After Bigram

原题说明

Given words first and second, consider occurrences in some text of the form “first second third“, where second comes immediately after first, and third comes immediately after second.

For each such occurrence, add “third“ to the answer, and return the answer.

 

Example 1:

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

Example 2:

Input: text = “we will we will rock you”, first = “we”, second = “will”
Output: [“we”,”rock”]

 

Note:

1. 1 <= text.length <= 1000
2. text consists of space separated words, where each word consists of lowercase English letters.
3. 1 <= first.length, second.length <= 10
4. first and second consist of lowercase English letters.

解题思路

题目的要求很简单，找出在first、second出现后紧跟着的第三个单词，而整句话是由空格和单词组成的。我们直接利用istringstream这个类处理串流，切分整句话，如果数组的当前元素的上一个元素等于second，且当前元素的上上一个元素等于first，就将当前元素添加进答案vector，最后返回记录答案的vector即可。

示例代码 (cpp)

class Solution {
public:
    vector<string> findOcurrences(string text, string first, string second) {
        istringstream ss(text);
        string firstStr = "";
        string secondStr = "";
        string cur;
        vector<string> ans;
        while (ss >> cur) {
            if (firstStr == first && secondStr == second) {
                ans.emplace_back(cur);
            }
            firstStr = secondStr;
            secondStr = cur;
        }
        return ans;
    }
};

示例代码 (java)

class Solution {
    public String[] findOcurrences(String text, String first, String second) {
        String a[]=text.split(" ");
       List<String> res=new ArrayList();int k=0;
        for(int i=0;i<a.length-2;)
        {
            if(a[i].equals(first) && a[i+1].equals(second))
            {
                res.add(a[i+2]);
               i=i+2;
            }
            else
                i++;
        }
        String temp[]=new String[res.size()];
        int i=0;
        for(String t: res)
        {
            temp[i]=t;i++;
        }
        return temp;
    }
}

示例代码 (python)

class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
        third = []
        sen = list(text.split())
        for i in range(1, len(sen)-1):
            if sen[i-1] == first and sen[i] == second:
                third.append(sen[i+1])
        return third

复杂度分析

时间复杂度: O(n)
空间复杂度: O(n)

视频讲解

我们在Youtube上更新了视频讲解，欢迎关注！