PAT-ADVANCED1071——Speech Patterns

我的PAT-ADVANCED代碼倉：https://github.com/617076674/PAT-ADVANCED

原題連結：https://pintia.cn/problem-sets/994805342720868352/problems/994805398257647616

題目描述：

題目翻譯：

1071 講話模式

人們通常在同一個詞的同義詞中有偏好。例如，有些人可能更喜歡“the police”，而有些人可能更喜歡“the cops”。分析這樣的模式可以幫助确認說話者的身份，這在驗證時很有用，例如，他是否仍然是網絡頭像背後的同一個人。

現在給出一段從某人的演講中抽樣的文本，你能找到這個人最常用的單詞嗎？

輸入格式：

每個輸入檔案包含一個測試用例。對每個測試用例，有一行長度不超過1048576個字元的文本，以回車符\n結束。輸入包含至少一個字母數字字元，即來自集合[0-9 A-Z a-z]的一個字元。

輸出格式：

對每個測試用例，在一行中列印輸入文本中最常出現的單詞，後跟空格和輸入中出現的次數。 如果有多個這樣的單詞，則列印按字典順序排列的最小單詞。 這個詞應該全部小寫。 這裡“單詞”被定義為由非字母數字字元或行開頭/結尾分隔的連續字母數字字元序列。

請注意，單詞不區分大小寫。

輸入樣例：

Can1: "Can a can can a can?  It can!"
           

輸出樣例：

can 5
           

知識點：字元串、計數

思路：用map集合統計每個單詞出現的次數

時間複雜度是O(n)，其中n為輸入字元串的字元數量。空間複雜度是O(m)，其中m為輸入字元串中不同單詞數量。

C++代碼：

#include<iostream>
#include<string>
#include<map>

using namespace std;

bool isPartOfWord(char c);

int main(){
	string input;
	getline(cin, input);
	for(int i = 0; i < input.length(); i++){
		if(input[i] >= 'A' && input[i] <= 'Z'){
			input[i] = input[i] - 'A' + 'a';
		}
	}
	map<string, int> wordMap;
	for(int i = 0; i < input.length(); i++){
		if(!isPartOfWord(input[i])){
			continue;
		}
		int j = i;
		while(isPartOfWord(input[j])){
			j++;
		}
		wordMap[input.substr(i, j - i)]++;
		i = j;
	}
	string result;
	int count = 0;
	for(map<string, int>::iterator it = wordMap.begin(); it != wordMap.end(); it++){
		if(it->second > count){
			result = it->first;
			count = it->second;
		}
	}
	cout << result << " " << count << endl;
	return 0;
}

bool isPartOfWord(char c){
	if((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')){
		return true;
	}
	return false;
}
           

C++解題報告：