作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址:https://leetcode.com/problems/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 <= text.length <= 1000
1 <= first.length, second.length <= 10
first
and second
consist of lowercase English letters.找出在一个长字符串text中,符合"first second third"模式的third。其中first和second是输入的。
对字符串进行分割,然后循环遍历,每次判断三个单词,看前两个是不是first和second,如果满足的话那么把第三个放到结果中即可。
时间复杂度是O(N)。
Python代码如下:
class Solution(object):
def findOcurrences(self, text, first, second):
"""
:type text: str
:type first: str
:type second: str
:rtype: List[str]
"""
words = text.split()
res = []
L = len(words)
for i in range(L - 2):
f, s, t = words[i], words[i + 1], words[i + 2]
if f == first and s == second:
res.append(t)
return res
C++代码的难点是字符串操作。C++竟然没有split()函数,这也是大家吐槽太多的点。一个可以替换的方案是使用stringstream类,该类会模拟字符串读入操作,即实现字符串按空格分割。初始化三个字符串,分别是f,s,t,读入到第三个里,前两个保留的是前两次读入的结果。这样进行判断是比较优雅的操作。
C++代码如下:
class Solution {
public:
vector<string> findOcurrences(string text, string first, string second) {
stringstream ss(text);
vector<string> res;
string f, s, t;
while (ss >> t) {
if (f == first && s == second)
res.push_back(t);
f = s;
s = t;
}
return res;
}
};
参考资料:
https://leetcode.com/problems/occurrences-after-bigram/discuss/308385/C%2B%2B-stringstream
2019 年 6 月 9 日 —— 简单的题没有难度,需要挑战有难度的才行
手机扫一扫
移动阅读更方便
你可能感兴趣的文章