UVA642 Word Amalgamation(查字典类)-蒲公英云

UVA642 Word Amalgamation(查字典类)

经典的查字典题+经典的map应用

题目描述

在美国各地的数百万份报纸中，有一款名为Jumble的文字游戏。这个游戏是要解决一个谜语，但为了找到答案中出现的字母来解读四个字是必要的。你的任务是编写一个可以解读单词的程序。

输入

输入文件包含4个部分： 1、字典，由至少一个，最多100个字组成，每行一个; 2、包含′XXXXXX′的行，表示字典的结尾; 3、一个或多个你必须解读的混乱的“单词”，每个单词都在一条线上; 4、包含’XXXXXX’的另一行，它表示文件的结尾。所有单词，包括字典单词和加扰单词，仅由小写英语组成字母，长度至少为一个，最多六个字符。（注意，哨兵’XXXXXX’包含多个大写X’。） 字典不一定按排序顺序，但字典中的每个单词都是独特的。

输出

对于输入中的每个加扰字，输出可以是的所有字典单词的字母列表。通过重新排列乱码中的字母而形成的。此列表中的每个单词都必须出现在一行中通过它自己。如果列表为空（因为不能形成字典单词），则输出“NOT A VALID WORD”有效的话，就不用输出。在任何一种情况下，输出一个包含六个星号的行来表示列表的结尾。

输入输出样例

输入 #1复制

tarp
given
score
refund
only
trap
work
earn
course
pepper
part
XXXXXX
resco
nfudre
aptr
sett
oresuc
XXXXXX

输出 #1复制

score
******
refund
******
part
tarp
trap
******
NOT A VALID WORD
******
course
******

思想总结：对字典进行映射，将要写入的词进行排序作为唯一的key，实际的词作为value。相同字母得到同一个key，而value则不同。

#include<bits/stdc++.h>
using namespace std;
struct node{
    string word[105];//相同字母的拼音 
    int count=0;//第几个拼音 
};
map<string,node> dict; //string为排序后的拼音，node为原拼音 
int main(){
    //写入字典 
    string s,temp;
    while(cin>>s&&s!="XXXXXX"){
        temp=s;//保存排序后的拼音 
        sort(temp.begin(),temp.end());
        dict[temp].word[dict[temp].count]=s;
        dict[temp].count++;
    }
    //比对字典 
    while(cin>>s&&s!="XXXXXX"){
        temp=s;
        sort(temp,temp.end());
        if(dict[temp].count!=0){//存在 
            sort(dict[temp].word,dict[temp].word+dict[temp].count);//word[]数组，则word就代表首地址 
            for(int i=0;i<dict[temp].count;i++){
                cout<<dict[temp].word[i]<<endl;    
            }    
            cout<<"******"<<endl;            
        }else{
            cout<<"NOT A VALID WORD"<<endl;
            cout<<"******"<<endl;
        }
    }
    return 0; 
}