1078. Bigram 分词
1078. Bigram 分词
题目
Given two strings 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
.
Return an array of all the words third
for each occurrence of "first second third"
.
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"]
Constraints:
1 <= text.length <= 1000
text
consists of lowercase English letters and spaces.- All the words in
text
are separated by a single space. 1 <= first.length, second.length <= 10
first
andsecond
consist of lowercase English letters.text
will not have any leading or trailing spaces.
题目大意
给出第一个词 first
和第二个词 second
,考虑在某些文本 text
中可能以 "first second third"
形式出现的情况,其中 second
紧随 first
出现,third
紧随 second
出现。
对于每种这样的情况,将第三个词 "third
" 添加到答案中,并返回答案。
示例 1:
输入: text = "alice is a good girl she is a good student", first = "a", second = "good"
输出:["girl","student"]
示例 2:
输入: text = "we will we will rock you", first = "we", second = "will"
输出:["we","rock"]
提示:
1 <= text.length <= 1000
text
由小写英文字母和空格组成text
中的所有单词之间都由 单个空格字符 分隔1 <= first.length, second.length <= 10
first
和second
由小写英文字母组成text
不包含任何前缀或尾随空格。
解题思路
- 首先将
text
按空格分割成一个单词数组arr
。 - 使用滑动窗口的方式遍历这个数组,维护
prev1
和prev2
分别为前两个单词。 - 从第三个单词开始,如果
prev1
和prev2
分别等于first
和second
,则将当前单词(即arr[i]
)加入结果数组。 - 更新
prev1
和prev2
,继续遍历。 - 返回记录的结果数组。
复杂度分析
- 时间复杂度:
O(n + m)
,其中n
是text
的长度,m
是arr
数组的长度。- 将字符串分割为数组的时间复杂度是
O(n)
。 - 遍历数组的时间复杂度是
O(m)
。
- 将字符串分割为数组的时间复杂度是
- 空间复杂度:
O(m)
,使用了额外的空间来存储数组arr
和结果数组res
代码
/**
* @param {string} text
* @param {string} first
* @param {string} second
* @return {string[]}
*/
var findOcurrences = function (text, first, second) {
const arr = text.split(' ');
let res = [];
let prev1 = arr[0],
prev2 = arr[1];
for (let i = 2; i < arr.length; i++) {
if (prev1 == first && prev2 == second) {
res.push(arr[i]);
}
prev1 = prev2;
prev2 = arr[i];
}
return res;
};