1078. Bigram 分词

🟢   🔖  字符串  🔗 力扣 LeetCode

题目

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 and second 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;
};