HDU 1113 Word Amalgamation （map 容器 + string容器） - c++编程基础

TOP

HDU 1113 Word Amalgamation （map 容器 + string容器）

2015-07-20 17:32:18 来源: 作者: 【大中小】浏览:2次

Tags：HDU 1113 Word Amalgamation map 容器 string

Problem Description

In millions of newspapers across the United States there is a word game called Jumble. The object of this game is to solve a riddle, but in order to find the letters that appear in the answer it is necessary to unscramble four words. Your task is to write a program that can unscramble words.

Input

The input contains four parts:

1. a dictionary, which consists of at least one and at most 100 words, one per line;
2. a line containing XXXXXX, which signals the end of the dictionary;
3. one or more scrambled `words' that you must unscramble, each on a line by itself; and
4. another line containing XXXXXX, which signals the end of the file.

All words, including both dictionary words and scrambled words, consist only of lowercase English letters and will be at least one and at most six characters long. (Note that the sentinel XXXXXX contains uppercase X's.) The dictionary is not necessarily in sorted order, but each word in the dictionary is unique.

Output

For each scrambled word in the input, output an alphabetical list of all dictionary words that can be formed by rearranging the letters in the scrambled word. Each word in this list must appear on a line by itself. If the list is empty (because no dictionary words can be formed), output the line ``NOT A VALID WORD instead. In either case, output a line containing six asterisks to signal the end of the list.

Sample Input

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

Sample Output

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

题意：先给你一些单词作为字典，在给一系列的单词查找字典中是否有这些单词（注意查找的单词，一个单词中的字母顺序是可以变得，也就是说单词之间只要字母是一样的不用考虑顺序一样都要输出）；如果字典中?有字母都相同的??就?出“NOT A VALID WORD”，?且每次都要?出一行“******”；

解?思路：

map容器是一?一?一的向量容器（??了解http://blog.csdn.net/keshacookie/article/details/19847781）

>>> 首先，?入一系列字典??，碰到“XXXXXX”?束；?些??作?向量的前端（後端也行，?人喜好，思路不要弄?就行了），在每?入一?字典??的?候，保存??的原?，然後再???排序，排序后的??作?向量的後端；

>>> 然後，?入加密后的??，先?加密???行排序，然後?map?面存?的字典??向量的後端?行比?（遍?一遍就OK了）；

>>> ???出就行了；

代?如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       //添加map?文件 #include 
       
         #include 
        
          #define RST(N)memset(N, 0, sizeof(N)) using namespace std; int flag; string s1, s2; //字符串容器； map 
         
           mp; //map容器 map 
          
            ::iterator it; //map迭代器 int main() { mp.clear(); //清空map容器 while(cin >> s1) { //?入字典?? if(s1 == XXXXXX) break; s2 = s1; //保存??的原??? sort(s1.begin(), s1.end()); mp[s2] = s1; //s1, s2形成向量，存?在map容器中 } while(cin >> s1) { //?入加密?? if(s1 == XXXXXX) break; flag = 0; sort(s1.begin(), s1.end()); for(it=mp.begin(); it != mp.end(); it++) { //遍?，?字符串?行比? string tmp = (*it).second; //map中first，second分?代表向量的前後端 if(s1 == tmp) { cout << (*it).first << endl; flag = 1; } } if(!flag) cout << NOT A VALID WORD << endl; cout << ****** << endl; } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：字符串函数---strcpy()与strncpy(..	下一篇：HDU 3949 XOR 高斯消元

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: