51nod 1095 Anigram单词【hash/map/排序/字典树】
2024-09-05 05:28:57
基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题
收藏
关注
一个单词a如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的Anigram,例如单词army和mary互为Anigram。现在给定一个字典,输入Q个单词,从给出的字典中找出这些单词的Anigram。
Input
第1行:1个数N,表示字典中单词的数量。(1 <= N <= 10000)
第2 - N + 1行,字典中的单词,单词长度 <= 10。
第N + 2行:查询的数量Q。(1 <= Q <= 10000)
第N + 3 - N + Q - 2行:用作查询的单词,单词长度 <= 10。
Output
共Q行,输出Anigram的数量,相同的2个单词不算Anigram,如果没有输出0。
Input示例
5
add
dad
bad
cad
did
3
add
cac
dda
Output示例
1
0
2 【分析】:一个map记录相同的(因为相同的2个单词不算Anigram,要减掉),一个记录排序后得到相同的单词。两者差值为Anigram的数量。
【代码】:
#include <bits/stdc++.h> using namespace std;
#define inf 1e18+100
#define LL long long const int maxn = ; int main()
{
int n,nn,x,y;
char s[maxn],ss[maxn];
map<string,int>m1,m2;
cin>>n;
for(int i=;i<n;i++)
{
scanf("%s",s);
m1[s]++;
sort(s,s+strlen(s));
m2[s]++;
}
cin>>nn;
for(int i=;i<nn;i++)
{
scanf("%s",ss);
x=m1[ss];
sort(ss,ss+strlen(ss));
y=m2[ss];
cout<<y-x<<endl;
}
}
最新文章
- MyBatis源码分析-SQL语句执行的完整流程
- jQuery的基本用法:
- mysql主从切换
- 单元测试 mock EF 中DbContext 和DbSet Include
- CentOS6.5菜鸟之旅:文件权限详解
- Fragment基础讲解
- css3 转换transfrom 过渡transition 和两个@
- 让AllocateHwnd接受一般函数地址作参数
- HDU4279(2012年天津网络赛---数论分析题)
- 国内APM企业的现状
- 【嵌入式开发】ARM 芯片简介 (ARM芯片类型 | ARM处理器工作模式 | ARM 寄存器 | ARM 寻址)
- Android相机启动crash错误排查
- CSS效果:焦点图片
- OJ:访问 const 成员函数问题
- mysql5.7.20完全卸载 win10
- Rest和Restful &; http
- json排序 及替换在字符串中全部替换某字符串
- Ubuntu配置Github并且新建仓库push代码,从已有仓库clone代码,并且push
- Postman&#160;Postman测试接口之POST提交本地文件数据
- asp.net mvc session锁问题 (转载)
热门文章
- 使用Unity做项目的时候,一些好的建议
- 《Cracking the Coding Interview》——第17章:普通题——题目7
- 《Cracking the Coding Interview》——第14章:Java——题目3
- adb启动和关闭
- 一个初学者的辛酸路程-前端js
- diskimage-builder element
- Leetcode with Python ->; Sort
- lowercase calligraphic letters
- iOS 实现设备应用之间的相互切换
- ocrosoft Contest1316 - 信奥编程之路~~~~~第三关 问题 I: 寻找大富翁