Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[LeetCode] 1078. Occurrences After Bigram #1078

Open
grandyang opened this issue May 30, 2019 · 0 comments
Open

[LeetCode] 1078. Occurrences After Bigram #1078

grandyang opened this issue May 30, 2019 · 0 comments

Comments

@grandyang
Copy link
Owner

grandyang commented May 30, 2019

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,又给了一段文字 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 同步地址:

#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 changed the title [LeetCode] 1078. Missing Problem [LeetCode] 1078. Occurrences After Bigram Mar 28, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant