What is the core pattern behind the Occurrences After Bigram problem?

The problem requires identifying adjacent triples of words that match a given bigram pattern. It's a string manipulation problem that focuses on comparing consecutive words.

How do I handle cases where there are no valid triples?

Simply return an empty array when no valid triples match the bigram pattern in the string.

What is the time complexity of solving the Occurrences After Bigram problem?

The time complexity is O(n), where n is the number of words in the input text, as we only need to iterate through the string once.

How can I optimize this solution for large inputs?

The solution is already quite efficient with O(n) time complexity. For very large inputs, ensure you're using efficient string splitting and comparison operations to avoid unnecessary overhead.

Can this problem be solved with a regular expression?

While regular expressions could be used, they are not the most straightforward solution. Splitting the string into words and iterating through them is more intuitive and efficient for this problem.

#1078

Easy

auto_awesomeString-driven solution strategy

LeetCode 题解工作台

Bigram 分词

给出第一个词 first 和第二个词 second ，考虑在某些文本 text 中可能以 "first second third" 形式出现的情况，其中 second 紧随 first 出现， third 紧随 second 出现。对于每种这样的情况，将第三个词 " third " 添加到答案中，…

字符串

题目描述

给出第一个词 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 不包含任何前缀或尾随空格。

lightbulb

解题思路

方法一：字符串分割

我们可以将字符串 $text$ 按照空格分割成字符串数组 $words$ ，然后遍历 $words$ ，如果 $words[i]$ 和 $words[i+1]$ 分别等于 $first$ 和 $second$ ，那么就将 $words[i+2]$ 添加到答案中。

遍历结束后，返回答案列表。

时间复杂度 $O(L)$ ，空间复杂度 $O(L)$ ，其中 $L$ 是 $text$ 的长度。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to recognize string manipulation patterns.
question_mark
Efficient handling of adjacent word comparisons.
question_mark
Understanding of time and space complexity for string operations.

warning

常见陷阱

外企场景

error
Overlooking cases where the bigram is not followed by a valid third word.
error
Incorrectly handling spaces or punctuation, which could affect word separation.
error
Misunderstanding the need to iterate through adjacent triples, rather than simply searching for individual words.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handle different forms of text input (e.g., multiple spaces or punctuation marks).
arrow_right_alt
Extend the problem to support variable-sized n-grams, not just bigrams.
arrow_right_alt
Optimize for cases with very large text inputs, considering time and space trade-offs.

help

常见问题

外企场景

继续练习

#1079 活字印刷 #1081 不同字符的最小子序列 #1071 字符串的最大公因子