UVa 156

題目

http://domen111.github.io/UVa-Easy-Viewer/?156

定義一個字串是 anagrams ，如果這個字串的任何排列方式除了本身以外都不是一個存在的單詞，我們就稱這個字串是 anagrams

現在給你很多的字串，這些字串組成了字典，問在這本字典當中有哪些字串是 anagrams

注意，在判斷 anagrams 時不需要理會大小寫

但是輸出時需要理會大小寫，並且依照字典序排序

想法

如果說字串 $A$ 經過排列後可以形成字串 $B$，那麼字串 $A, B$ 分別經過排序之後得到的 $A’, B’$ 也就會相等

依照這樣的性質，我們建立一個新的結構(struct)，紀錄字典當中每個字轉成小寫並且經過排序後的樣子、以及原字串在字典當中的編號

那麼這個新的結構所組成的新字串陣列在經過排序之後，根據上面所得到的性質我們會發現，那些排列後相同的字串都會被排在一起

接下來我們只要篩掉這些字串，把剩餘的字串再透過編號對應回原本的字串，我們就拿到還沒排序過的答案了

最後經過排序就是正解

Code

//By Koios1143
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

struct words{
	string word;
	int id;
};

int i=0, l=0;
string input, dict[1005], output[1005];
words word[1005];

bool cmp(words p, words q){
	if(p.word.compare(q.word)!=0) return p.word < q.word;
	return false;
}

int main(){
	while(cin>>input && input.compare("#")!=0){
		// 字典先存放一份原始檔
		dict[i] = input;
		
		// 都先轉換成小寫
		for(int j=0 ; j<input.size() ; j++){
			input[j] = tolower(input[j]);
		}
		// 接者把字串排序好
		sort(input.begin(), input.end());
		//放進新的結構當中
		word[i].word = input;
		word[i].id = i;
		i++;
	}
	// 把新的結構所形成的陣列排序
	sort(word, word+i, cmp);
	for(int j=0, k ; j<i ; ){
		for(k=j ; k<i ; k++){
			if(word[j].word.compare(word[k].word)!= 0) break;
		}
		if(k - j == 1){
			// 是 anagrams
			output[l++] = dict[word[j].id];
			j++;
		}
		else{
			// 不是 anagrams
			j = k;
		}
	}
	// 輸出結果要排序
	sort(output, output+l);
	for(int j=0 ; j<l ; j++){
		cout<<output[j]<<"\n";
	}
	return 0;
}

時間複雜度分析

輸入時間複雜度 $O(n)$，$1 \leq n \leq 1000$

假設每個單詞的長度為 $s_i$， $S = \sum_{i = 0}^{n-1}s_i$

建立新陣列的時間複雜度為 $O(S + \sum_{i = 0}^{n-1}s_ilog{s_i})$

排序新陣列的時間複雜度為 $O(nlogn)$

篩選的時間複雜度為 $O(n)$

輸出結果排序時間複雜度約為 $O(nlogn)$

輸出時間複雜度約為 $O(n)$

總時間複雜度約為 $O(3n + nlogn + S + \sum_{i = 0}^{n-1}s_ilog{s_i})$