给定一个单词和文本，我们需要回到字谜的发生 [英] Given a word and a text, we need to return the occurrences of anagrams

问题描述

给定一个字和一个文本，返回在文本字字谜的出现的计数。 对于如。词是供和文本是forxxorfxdofr，为，将氧自由基，羊口疮，来来往往等，所以答案应该是3这个特殊的例子。

Given a word and a text, return the count of the occurrences of anagrams of the word in the text. For eg. word is "for" and the text is "forxxorfxdofr", anagrams of "for" will be "ofr", "orf","fro", etc. So the answer would be 3 for this particular example.

我已经得到了强力的做法，越来越单词的所有排列，然后进行比较，如果文本包含它，并增加出现的次数，但这是O（N ^ 2）的方法。我在寻找一个更好的复杂性。

I have got the brute force approach which is getting all the permutations of the word, then compare if the text contains it, and increase the number of occurrences, but that is O(N^2) approach. I'm looking for a better complexity.

推荐答案

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

You can simply look for the character count.

例如说你正在寻找看的anagramms。所以，你要寻找的：

Say for example that you're looking for anagramms of look. So, you're looking for:

• 4 charachter长度字，
• 与1升，2 O和1K的。

简单地处理了前4个字母，存储计数。检查是否有匹配。 添加下一个字符（增量），删除旧的字符（递减）。再检查一遍。 等等...

Simply process the first 4 letters, store the counts. Check whether you have a match. Add the next character (increment), remove the old character (decrement). Check again. And so on...

这篇关于给定一个单词和文本，我们需要回到字谜的发生的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！