792. Number of Matching Subsequences 寻找子串数量

原题&翻译

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

给出一个字符串 S 和一个单词字典 words,判断 words[i] 是否为 S 的子串。

  • S 和 Words 中所有字符均为小写字母。

  • S 长度在 [1, 50000] 范围内。

  • words 长度限制在 [1, 5000] 范围内。

  • words 中的字符串长度限制在 [1, 50] 范围内。


解题思路

超时的方法

把超时方法也列出来,是因为它可能有点价值吧,哦那个通常的方法处理这道题,比如这个代码,挨个匹配,妥妥的超时。

不超时的方法

这里呢,我们注意到一共就 26 个字母,我们只需要处理一下原数据,把原来的 S 的索引按照字符顺序存入 letter(26) 中。和 words[i] 匹配的时候,只需要判断该字母是否存在于 letter 中即可(还需要判断索引是否大于之前)。两百多 ms,还是很慢的。

春草年年绿,王孙归不归?

Hello world!
文章已创建 197

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部