Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-01SRM391 (Practice)

SRM 391 IsomorphicWords

|  SRM 391 IsomorphicWords - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 391 IsomorphicWords - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8175

  • 方針を検討
    • 各文字列ペアに対して、Isomorphicかどうか確認する
    • 先頭から1文字ずつ比較してmapに突っ込んで、矛盾(既に他の文字にマップ済)しなければOKでよさそう
  • サンプル通らない。なんで・・・
    • 問題文に戻る。
    • 同じ文字にマップしちゃいけないのか、アブナイアブナイ
    • マップ済の文字をメモしておき、2度出現したら false を返すように変更
  • サンプル通った。
    • 自明なケース {a, b}などを確認
    • !?このサンプル文字列長が全部同じじゃないか!?
      • All elements of words will have the same length. あ、そうですか・・・よかった
  • 提出

public class IsomorphicWords {
	int al;
	public boolean isok(String a, String b) {
		char[] map = new char[512];
		boolean[] used = new boolean[512];
		for (int i = 0 ; i < al ; i++) {
			char ca = a.charAt(i);
			char cb = b.charAt(i);
			if (map[ca] == 0) {
				map[ca] = cb;
				if (used[cb]) {
					return false;
				}
				used[cb] = true;
			} else if (map[ca] != cb) {
				return false;
			}
		}
		return true;
	}
	
	
	public int countPairs(String[] words) {
		int len = words.length;
		al = words[0].length();
		int count = 0;
		for (int i = 0 ; i < len ; i++) {
			for (int j = i + 1 ; j < len ; j++) {
				if (isok(words[i], words[j])) {
					count++;
				}
			}
		}
		return count;
	}
}