一尘不染

给定一个单词和一个文本,我们需要返回字谜的出现

algorithm

给定一个单词和一个文本,返回该单词在文本中出现字谜的次数。例如。单词是“ for”,文本是“ forxxorfxdofr”,“ for”的字样将是“
ofr”,“ orf”,“ fro”等。因此,对于此特定示例,答案为3。

我有蛮力方法,它获取单词的所有排列,然后比较文本是否包含单词,并增加出现次数,但这是O(N ^ 2)方法。我正在寻找更好的复杂性。


阅读 276

收藏
2020-07-28

共1个答案

一尘不染

您可以简单地查找字符数。

举例来说,您正在寻找的字谜look。因此,您正在寻找:

  • 4个字符长度的单词,
  • 1 l,2 o和1 k。

只需处理前4个字母,存储计数。检查您是否有比赛。添加下一个字符(递增),删除旧字符(递减)。再检查一遍。等等…

2020-07-28