1078. Occurrences After Bigram

置顶

Created At : 2023-10-28 15:14

Count:636 Views 👀 :

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 <= text.length <= 1000
text consists of space separated words, where each word consists of lowercase English letters.
1 <= first.length, second.length <= 10
first and second consist of lowercase English letters.

这道题说是给了两个单词 first 和 second，又给了一段文字 text，现在让找出所有紧跟着 first 和 second 后面的第三个单词。这道题标记为 Easy，其实也没什么难度，首先就是要把 text 中的单词都拆分出来，此时又到了羡慕 Java 有 split 函数，吐槽 C++ 的功能不够强大的时间了。没办法，谁让博主老早就上了 C++ 这条贼船了呢，老老实实的用字符串流类吧，新建一个数组 words，用来保存分离出来的单词。对于每个单词，看下其前面的两个单词是否分别等于 first 和 second，等于的话就将当前单词加入到结果 res 中即可，最后别忘了还要将当前单词加入 words 数组，参见代码如下：

解法一：

class Solution {
public:
    vector<string> findOcurrences(string text, string first, string second) {
        vector<string> res, words;
        istringstream iss(text);
        string t;
        while (iss >> t) {
            int n = words.size();
            if (n >= 2 && words.back() == second && words[n - 2] == first) res.push_back(t);
            words.push_back(t);
        }
        return res;
    }
};

其实我们并不用保存所有的单词，因为这里只关心前两个单词是啥，所以可以使用两个变量 pre2 和 pre 来记录前面的两个单词，当其分别等于 first 和 second 的时候，将当前单词加入结果 res 中，并且 pre2 赋值为 pre，pre赋值为当前单词即可，参见代码如下：

解法二：

class Solution {
public:
    vector<string> findOcurrences(string text, string first, string second) {
        vector<string> res, words;
        istringstream iss(text);
        string t, pre, pre2;
        while (iss >> t) {
            if (pre2 == first && pre == second) res.push_back(t);
            pre2 = pre;
            pre = t;
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1078

参考资料：

https://leetcode.com/problems/occurrences-after-bigram/

https://leetcode.com/problems/occurrences-after-bigram/discuss/308385/C%2B%2B-stringstream

https://leetcode.com/problems/occurrences-after-bigram/discuss/308224/JavaPython-3-Split-String.

LeetCode All in One 题目讲解汇总(持续更新中…)

转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com