程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1113 Word Amalgamation （map 容器 + string容器）

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

編輯：C++入門知識

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;
}