题目
一个单词a如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的Anigram,例如单词army和mary互为Anigram。另:相同的2个单词不算Anigram。现在给定一个字典,输入Q个单词,从给出的字典中找出这些单词的Anigram。
思路
一个map保存原串出现次数,一个map保存排序串出现次数,减一下
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| #include<bits/stdc++.h> #define ll long long #define db double using namespace std; int n,q; char s[20],sp[20]; map<string,int>mp1; map<string,int>mp2; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>s; strcpy(sp,s); sort(sp,sp+strlen(sp)); mp1[s]++; mp2[sp]++; } cin>>q; for(int i=1;i<=q;i++){ cin>>s; strcpy(sp,s); sort(sp,sp+strlen(sp)); cout<<mp2[sp]-mp1[s]<<endl; } return 0; }
|