当前位置: 代码迷 >> 综合 >> LeetCode-1078:找出连续双单词后的单词(Occurrences After Bigram)
  详细解决方案

LeetCode-1078:找出连续双单词后的单词(Occurrences After Bigram)

热度:77   发布时间:2023-12-14 00:23:15.0

给出第一个词 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 由一些用空格分隔的单词组成,每个单词都由小写英文字母组成
1 <= first.length, second.length <= 10
first 和 second 由小写英文字母组成

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 = []for i in range(2, len(words)):if words[i-2]==first and words[i-1]==second:res.append(words[i])return res"""return [words[i] for i in range(2, len(words)) if words[i-2]==first and words[i-1]==second]

C语言实现:
解题思想是:将first和second按照first+’ ‘+second+’ '合并成一个新的字符串subStr;在text中查找subStr,找到位置后,再查找subStr后的第一个单词。

根据题目的备注中的第一条和第二条约束,text最多有500个单词组成。我们定义一个长度为500的字符串数组,临时保持找到的third。这么做,是因为我们无法确定到底能找到多少个third。我不想找到一个就用realloc动态调整返回数组。

first和second的长度不超过10,加上两个空格,所以subStr最大长度不超过22,我们用字符数组存储。

代码如下:
在这里插入图片描述
代码16行,开始查找;

代码17行,查找text中subStr字串的起始地址;

代码19行,如果找到了,注意这个子串是以subStr开头的,我们要找到的是third,所以我要对找到子串位置再调整,以跳过subStr,这时候p就是third的起始地址,后面我们只要再获取它的长度即可;

代码20行,对调整后的子串,查找左边的空格地址t,这时候有两种情况:

  1. 找到了空格,那么third的长度就是t-p;
  2. 没找到空格,表示p子串已经是text的结尾,那么third的长度就是字串p的长度。注意这个时候strlen§可能是0,即text的结尾就是"first second \n";

代码22~25行:分配内存保持找到的third。对于长度是0的情况要跳过。最后,创建返回数组res,并完成填充后返回。