Bigram 分词

难度: Easy

给出第一个词 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 由小写英文字母组成

Submission

运行时间: 10 ms

内存: 16.0 MB

class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
        ans = []
        text = text.split()
        for i in range(len(text) - 2):
            if text[i] == first and text[i + 1] == second:
                ans.append(text[i + 2])
        return ans

Explain

题解的思路是首先将输入的文本字符串 `text` 通过 split() 方法分割成单词列表。然后，遍历这个列表，检查每个位置 i 的单词及其后的两个单词是否符合给定的 `first` 和 `second`。如果当前单词是 `first` 并且下一个单词是 `second`，则将第三个单词（即位置 i+2）添加到结果列表中。最后，返回结果列表。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
        ans = []  # 初始化结果列表
        text = text.split()  # 将输入文本分割成单词列表
        for i in range(len(text) - 2):  # 遍历单词列表，注意防止索引越界
            if text[i] == first and text[i + 1] == second:  # 检查是否满足 first 后跟 second
                ans.append(text[i + 2])  # 如果满足，将第三个单词添加到结果列表
        return ans  # 返回结果列表

Explore

在实现中，我通过将循环的终止条件设置为 `len(text) - 2` 来处理边界条件。这种方式确保了只有当列表中至少有三个单词时，循环才会执行。如果单词数量少于三个，那么 `len(text) - 2` 将会小于0，导致循环不执行，因此代码自然地处理了单词数量不足的情况，不会引发索引越界的错误。

这个算法确实考虑了文本中可能存在的连续重复的 'first second' 模式。当算法遍历到每个单词时，它都会检查该单词及其后面的单词是否符合 'first second' 的模式。如果符合，算法会将后面的第三个单词添加到结果列表中。这个过程会在每个可能的位置重复进行，因此即使 'first second' 模式在文本中连续出现，算法也能逐一找到并处理它们。

在遍历单词列表时，我选择忽略最后两个单词是为了防止索引越界。因为算法需要访问当前单词后的第二个和第三个单词，如果当前索引已经是列表末尾或倒数第二个位置，就无法获取这两个单词。另一种方法是使用 `try-except` 结构，允许循环遍历整个列表，但在访问索引时添加异常处理来捕获越界错误。这种方法可以遍历整个列表，但可能会使代码复杂且效率略降。

如果输入的文本非常长，这种基于线性搜索的方法性能可能会受影响，因为它需要遍历整个单词列表并多次访问索引。为了提高处理大数据量的效率，可以考虑以下优化策略：1. 使用更高效的数据结构，如索引数组或散列映射，以快速定位 'first' 和 'second' 单词的位置。2. 并行处理，将文本分割成多个部分，在多个线程或进程中并行查找，然后合并结果。这些优化可以帮助减少处理时间，特别是在处理非常大的数据集时。