UVA642 Word Amalgamation(查字典类)

Love The Way You Lie 2023-06-13 14:28 14阅读 0赞

经典的查字典题+经典的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; 
    }