SRM 391 250pt: IsomorphicWords

問題概要

文字列がN(<50)個与えられる。文字の置換で同型になるペアが何通りあるか求める問題。

考えたこと

• 色々やり方がありそう。
• 数字に変換して比較するか。
• 一番愚直な方法で書く。余計なことはしない。
• 問題なく通った。

practiceで通ったコード

計算量O(N^2 * L)

#include <vector>
#include <string>
using namespace std;

struct IsomorphicWords {

	int countPairs(vector <string> words) {
		const int N = words.size();

		//vector<int>に変換
		vector< vector<int> > vs(N);
		for(int i=0; i<N; i++){
			vs[i].assign(words[i].length(), 0);
			int cnt = 1;
			for(int j=0; j<(int)vs[i].size(); j++)if(vs[i][j] == 0){
				char ch = words[i][j];
				for(int k=0; k<(int)words[i].length(); k++){
					if(words[i][k] == ch){
						vs[i][k] = cnt;
					}
				}
				cnt++;
			}
		}

		int ret = 0;
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				if(vs[i] == vs[j]){
					ret++;
				}
			}
		}
		return ret;
	}

};