Application of the purple book p113map of ananagrams (uva156)

Purple Book P113;map Application ;UVa146 Ananagrams;

Vjudge Please click here for the title link

The main idea of the topic ：

Enter some words （ The input contains several lines , No more than 80 Characters , It consists of some words . Words by no more than 20 Upper and lower case letters ）, Find all the words that meet the following conditions ： The word cannot be rearranged by letters , Get another word of the input text . When judging whether the conditions are met , Letters are not case sensitive , However, the input case should be kept when outputting , In dictionary order .

Sample Input
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

Sample Output
Disk
NotE
derail
drIed
eye
ladder
soon

Topic analysis （ The idea is based on the purple book ）：

The question asks to find out “ No repetition ” 's words , So how to judge “ repeat ” Is the key point of this topic ;
Given in the title “ repeat ” Means ： Two words with the same number of letters , There is no requirement for alphabetical order .

data structure choice ： because map The property of having a value corresponding to a key , It can easily help us count the number of times each word appears , Easy to remove heavy , We can choose to build one map To store the number of occurrences of different words .

Algorithm design ：map The rational use of can help us simplify the code , But we still need one that can be used efficiently map To achieve the choice of goals ; Since the title requires “ repeat ” There is no alphabetical order , Then we can put the order of the letters in the words Unification To facilitate comparison ： Convert all letters to lowercase and sort them in dictionary order ;

void change(string& now)
{
    
	 for(int i=0;i<now.length();i++)
	 	 now[i]=tolower(now[i]);
	 sort(now.begin(),now.end());
	 return ;
}

Then compare the words according to the unified words ;

Module design ： Definition and pretreatment – Input and initialization – Simulation judgment – Output –return 0;

Code ：

#include<map>
#include<iostream>
#include<string>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;

vector<string> txt;
map<string,int> words;
vector<string> answer;
string s;

//txt Save all the words you read ,words Save the initialized word and its occurrence times ,answer Save words that only appear once 

void change(string& now);

int main()
{
    
	 while(cin>>s)
	 {
    
	 	 if(s=="#") break; // encounter # End reading 
	 	 txt.push_back(s);
	 	 string now(s);
	 	 change(now);      // initialization 
	 	 words[now]++;     // Count the times 
	 }
	 for(int i=0;i<txt.size();i++)
	 {
    
	 	 string now(txt[i]);
	 	 change(now);
	 	 if(words[now]==1) answer.push_back(txt[i]);
	 }
	 sort(answer.begin(),answer.end());   // The output should be sorted in dictionary order 
	 for(int i=0;i<answer.size();i++) cout<<answer[i]<<endl;
	 return 0;
}

void change(string& now)
{
    
	 for(int i=0;i<now.length();i++)
	 	 now[i]=tolower(now[i]);
	 sort(now.begin(),now.end());
	 return ;
}

Summary of key points and details ：

1. Flexible use map The correspondence between the middle key and the value , Choose according to the scene ;
2. sort Two cases of use <1. sort(a,a+n) <2. sort(m.begin(),m.end());

Updated on 2020.6.24