UVA-156

Most crossword puzzle fans are used to anagrams — groups of words with the same letters in differentorders — for example OPTS, SPOT, STOP, POTS and POST. Some words however do not have thisattribute, no matter how you rearrange their letters, you cannot
form another word. Such words arecalled ananagrams, an example is QUIZ.Obviously such definitions depend on the domain within which we are working; you might thinkthat ATHENE is an ananagram, whereas any chemist would quickly produce ETHANE. One possibledomain
would be the entire English language, but this could lead to some problems. One could restrictthe domain to, say, Music, in which case SCALE becomes a relative ananagram (LACES is not in thesame 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 relativeananagrams. 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.InputInput
will consist of a series of lines. No line will be more than 80 characters long, but may contain anynumber of words. Words consist of up to 20 upper and/or lower case letters, and will not be brokenacross lines. Spaces may appear freely around words, and at
least one space separates multiple wordson the same line. Note that words that contain the same letters but of differing case are considered tobe anagrams of each other, thus ‘tIeD’ and ‘EdiT’ are anagrams. The file will be terminated by a lineconsisting of
a single ‘#’.OutputOutput will consist of a series of lines. Each line will consist of a single word that is a relative ananagramin the input dictionary. Words must be output in lexicographic (case-sensitive) order. There will alwaysbe at least one relative
ananagram.Sample Inputladder came tape soon leader acme RIDE lone Dreis peatScAlE orb eye Rides dealer NotE derail LaCeS drIednoel dire Disk mace Rob dries#Sample OutputDiskNotEderaildrIedeyeladdersoon

题解：就是查找字母重组后出现一次的单词；先将单词变为小写并按字典序排列，用map容器存储单词，然后用其映射

表示出现其次数。最后将出现一次的单词保存到set中，将其输出。

AC代码为：

#include<iostream>

#include<string>

#include<sstream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

map<string,int> s;

vector<string>words;

string tr(string &s)

{ string ss=s;

for(int i=0;i<ss.length();i++)

{

ss[i]=tolower(ss[i]);

}

sort(ss.begin(),ss.end());

return ss;

}

int main()

{

string st;

while(cin>>st)

{

if(st[0]=='#')break;

string r=tr(st);

words.push_back(st);

if(s.count(r)==0)s[r]=1;

else s[r]++;

}

vector<string>ans;

for(int i=0;i<words.size();i++)

{

if(s[tr(words[i])]==1)ans.push_back(words[i]);

}

sort(ans.begin(),ans.end());

for(int i=0;i<ans.size();i++)

{

cout<<ans[i]<<endl;

}

return 0;

}

巴特西

UVA-156

最新文章

热门文章