简单来说
输入一些单词,找出所有满足如下条件的单词:该单词不能通过字母重排,得到输入文本中的另外一个单词。 在判断是否满足条件时,字母不分大小写,但在输入时应保留输入中的大小写,按字典序进行排列(所有大写字母在小写字母的前面)。
原文楔子:
Most crossword puzzle fans are used to anagrams — groups of words with the same letters in different orders — for example OPTS, SPOT, STOP, POTS and POST. Some words however do not have this attribute, no matter how you rearrange their letters, you cannot form another word. Such words are called ananagrams, an example is QUIZ. Obviously such definitions depend on the domain within which we are working; you might think that ATHENE is an ananagram, whereas any chemist would quickly produce ETHANE. One possible domain would be the entire English language, but this could lead to some problems. One could restrict the domain to, say, Music, in which case SCALE becomes a relative ananagram (LACES is not in the same domain) but NOTE is not since it can produce TONE. Write a program that will read in the dictionary of a restricted domain and determine the relative ananagrams. Note that single letter words are, ipso facto, relative ananagrams since they cannot be “rearranged” at all. The dictionary will contain no more than 1000 words.
大多数填字游戏爱好者习惯于字谜 - 具有不同顺序的相同字母的单词组 - 例如OPTS,SPOT,STOP,POTS和POST。然而,有些单词没有这个属性,无论你如何重新排列它们的字母,你都不能形成另一个单词。这样的单词被称为anaanagrams,一个例子是QUIZ。显然,这些定义取决于我们工作的领域;你可能会认为ATHENE是一个anatragram,而任何化学家都会很快产生乙烷。一个可能的领域是整个英语,但这可能会导致一些问题。人们可以将域限制为音乐,在这种情况下,SCALE成为相对的anamanogram(LACES不在同一域中),但NOTE不是,因为它可以产生TONE。编写一个程序,该程序将在受限制域的字典中读取并确定相对分析法。请注意,单字母单词本身是相对的拟人解图,因为它们根本无法“重新排列”。字典将包含不超过1000个单词。
输入
Input will consist of a series of lines. No line will be more than 80 characters long, but may contain any number of words. Words consist of up to 20 upper and/or lower case letters, and will not be broken across lines. Spaces may appear freely around words, and at least one space separates multiple words on the same line. Note that words that contain the same letters but of differing case are considered to be anagrams of each other, thus ‘tIeD’ and ‘EdiT’ are anagrams. The file will be terminated by a line consisting of a single ‘#’.
输入将由一系列行组成。任何行的长度都不会超过 80 个字符,但可以包含任意数量的单词。单词最多由 20 个大写和/或小写字母组成,并且不会跨行分隔。空格可以自由出现在单词周围,并且至少有一个空格将同一行上的多个单词分开。请注意,包含相同字母但大小写不同的单词被认为是彼此的字谜,因此“tIeD”和“EdiT”是字谜。输入以 # 结束。
输出
Output will consist of a series of lines. Each line will consist of a single word that is a relative ananagram in the input dictionary. Words must be output in lexicographic (case-sensitive) order. There will always be at least one relative ananagram.
输出将由一系列行组成。每行将包含一个单词,该单词是输入字典中的相对分析词。单词必须按词典(区分大小写)顺序输出。始终至少有一个相对分析图。
输入样例
ladder came tape soon leader acme RIDE lone Dreis peat ScAlE orb eye Rides dealer NotE derail LaCeS drIed noel dire Disk mace Rob dries #
输出样例
Disk NotE derail drIed eye ladder soon
#include<iostream>
#include<set>
#include<unordered_map>
#include<algorithm>
using namespace std;
string standard(string temp){
for(auto & it:temp)it=tolower(it);
sort(temp.begin(),temp.end());
return temp;
}
int main(){
string temp;
set<string> words;
unordered_map<string,int> wonderful;
while(cin>>temp){
if(temp=="#")break;
words.insert(temp);
wonderful[standard(temp)]++;
}
for(auto & it:words)if(wonderful[standard(it)]==1)cout<<it<<endl;
}
算法竞赛入门经典-映射:map,这道题是紫书上用来讲map的,原书采用的解法和我的大同小异。书上的解法是先把每一个单词存进一个vector对象里面,然后将单词标准化(大写变小写,重新排序字母)的结果作为map的key,并记录次数作为map的值,然后遍历vector对象里面存的原单词,去查看该单词在map里面的值,输出值为1的单词。
我的思路和书上大体一样,但我的更加简洁,原书用了40行代码,我用了20行,因为我用的是set和unordered_map,而不是vector和map,set可以自动排序,不需要自己再去调用sort。而map和unordered_map功能好像是一样的,可以把我代码里面所有unordered_map直接换成map,照样可以运行出正确结果,但只是功能差不多一样,map是有序的,内部是一个严格的红黑树,而unordered_map内部是个哈希表,是无序的,在查找元素上,哈希表效率高。