java 字謎

Problem statement:

問題陳述：

Given a string S and a word C, return the count of the occurrences of anagrams of the word in the text. Both string and word are in lowercase letter.

給定一個字符串S和一個單詞C ，返回該單詞在文本中的字謎出現的次數 。 字符串和單詞均為小寫字母。

Examples:

例子：

    Input:
S=fororfrdofr
C=for
Output:
3
Input:
S=aabaabaa
C=aaba
Output:
4

Example with explanation:

帶有說明的示例：

Anagrams:

字謎：

Two words are known to be anagrams of each other if they are of same length & use same set of characters with same frequencies.

如果兩個單詞的長度相同并且使用相同頻率的相同字符集，則兩個單詞彼此稱為字謎。

"aba" and "baa" are anagrams since both have two a's and one b.

“ aba”和“ baa”是七巧板，因為它們都有兩個a和一個b 。

"aba" and "bab" are not anagrams.

“ aba”和“ bab”不是字謎。

For the First example:

對于第一個示例：

    Input:
S=fororfrdofr
C=for
S:
0	1	2	3	4	5	6	7	8	9	10
f	o	r	o	r	f	r	d	o	f	r
S(0,2): for
Thus S(0,2) is anagram of w
S(3,5) : orf
Thus S(3,5) is anagram of w
S(8,10) : ofr
Thus S(8,10) is anagram of w
Thus count of occurrences of anagrams: 3

Pre-requisite:

先決條件：

1. FUNCTION to check whether to word is anagram or not

   檢查單詞是否為字謎的功能

   Check(string s1, string s2): returns true or false based or anagram detection

   Check(字符串s1，字符串s2) ：返回基于true或false的或字謎檢測

2. String::substr(int i,int j): returns substring of length j from index i

   String :: substr(int i，int j) ：從索引i返回長度為j的子字符串

Algorithm:

算法：

    1.  Set count=0;
For i=0:i<a.length()-b.length()+1
IF (check(a.substr(i,b.length()),b))
count++;
2.  Print count

So the idea is pretty simple. What we are doing is to slide the window and check for anagrams. Window is nothing but the substring being extracted every time. Window length is equal to the word length.

所以這個想法很簡單。 我們正在做的是滑動窗口并檢查字謎。 Window只是每次提取的子字符串。 窗口長度等于字長。

To check anagrams

檢查字謎

FUNCTION check(string a, string b)
1.  Declare a map m; //to store frequency of each character
2.  For string abuild the map
For (int i=0;i<a.length();i++)
m[a[i]]++;
END FOR
3.  For string bdestruct the map.
For (int i=0;i<b.length();i++)
m[b[i]]--;
END FOR
4.  If map is totally destructed that means all key has value perfectly 0 
return true;
Else 
Return false.
END FUNCTION

So this basically means, we are constructing a container using the elements of string a. Then we are destructing the map to form string b. If such formation is possible they strings are anagrams of each other.

因此，這基本上意味著，我們正在使用字符串a的元素構造一個容器。 然后，我們將映射銷毀以形成字符串b。 如果這樣的形成是可能的，則它們的弦是彼此的字謎。

C++ implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
bool check(string a,string b){
//checking anagrams
map<char,int> m;
for(int i=0;i<a.length();i++)
m[a[i]]++;
for(int i=0;i<b.length();i++)
m[b[i]]--;
for(auto it=m.begin();it!=m.end();it++)
if(it->second!=0)
return false;
return true;
}
int countNoOfAnagram(string a,string b){
int count=0;
//sliding window
for(int i=0;i<a.length()-b.length()+1;i++){
if(check(a.substr(i,b.length()),b))
count++;
}
return count;
}
int main()
{
string S,C;
cout<<"Enter string S and word C\n";
cin>>S>>C;
cout<<"No of anagrams: "countNoOfAnagram(S,C)<<endl;
return 0;
}

Output

輸出量

Enter string S and word C
fororfrdofr
for
No of anagrams: 3

翻譯自: https://www.includehelp.com/icp/count-occurrences-of-anagrams.aspx

java 字謎