UVa 10815 題解 — C++

此筆記為UVa 10815的題目詳解，包含解題思路、C++範例程式碼。

Andy's First Dictionary (OnlineJudge 10815)

題目

Andy, 8, has a dream - he wants to produce his very own dictionary. This is not an easy task for him, as the number of words that he knows is, well, not quite enough. Instead of thinking up all the words himself, he has a briliant idea. From his bookshelf he would pick one of his favourite story books, from which he would copy out all the distinct words. By arranging the words in alphabetical order, he is done! Of course, it is a really time-consuming job, and this is where a computer program is helpful.

You are asked to write a program that lists all the different words in the input text. In this problem, a word is defined as a consecutive sequence of alphabets, in upper and/or lower case. Words with only one letter are also to be considered. Furthermore, your program must be CaSe InSeNsItIvE. For example, words like “Apple”, “apple” or “APPLE” must be considered the same.

輸入 / 輸出說明

輸入說明	輸出說明
The input file is a text with no more than 5000 lines. An input line has at most 200 characters. Input is terminated by EOF.	Your output should give a list of different words that appears in the input text, one in a line. The words should all be in lower case, sorted in alphabetical order. You can be sure that he number of distinct words in the text does not exceed 5000.

解題思路

利用集合 set 的特性解決問題，因為 set 是同樣的內容只儲存一次，而且會自動以升序排列，因此就可以直接幫我們得到題目要求的答案。

而我們要做的就是輸入一個字串後，分別抓出字串中的單詞，他可能包含在特殊符號中，也可能出現到最後，因此我們只需要在遇到英文字母時將他變成小寫後暫存在 word 中，而在遇到特殊符號或結尾時，將已儲存的單字加入 set 中即可。

範例程式碼

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, n;
	string s;
	char word[5000];
	set <string> set;
	
	while (getline(cin, s)) {
	    memset(word, ' ', sizeof(word));
		n = 0;
		
		for (i=0;i<s.size();i++) {
			if (isalpha(s[i])) {  //是英文字母 
				word[n] = tolower(s[i]);  //轉小寫字母 
				n++;
			}
			else {  //不是英文字母
			    word[n] = '\0';
				if (n > 0)  //有單詞 
					set.insert(word);  //加入 set 中 
					
				n = 0;
			}
		}
		if (n > 0) {  //結尾可能還有單詞沒加入 set 
		    word[n] = '\0';
			set.insert(word);
		}
	}
	
	for (string key: set)
		cout << key << endl; 

	return 0;
}

運行結果

AC 0.000 s

tags: CPE 2星

查看更多資訊請至：https://www.tseng-school.com/