String Transformation [AtCoder Beginner Contest 110 C]

atcoder.jp

Sに含まれる文字を「変換元」、Tに含まれる文字を「変換先」と呼ぶことにします。このとき、変換先はただ1つであり、変換元も同様にただ1つである必要があります。

仮に S=abb, T=xyz の場合を考えてみます。変換操作では、1種類の文字を別の1種類の文字と交換することしかできないので、bb を yz に変えることができません。よって、変換先はただ1つである必要があります。

また、S=abc, T=xxy の場合を考えてみます。変換操作によって a と x を交換すると、Sは xbc になります。次に、b を x にしようとして、b と x を交換すると、Sは bxc になってしまい、上手くいきません。よって、変換元はただ1つである必要があります。

入力例2を見てみます。

S：chokudai
T：redcoder

Tに含まれる r の変換元が、c,i の2種類あります。また、dの変換元も o,d の2種類あります。上記の条件を満たしていないので、答えは No となります。

以上のことをまとめると、

・S の i 番目の文字は T に含まれるただ1つの文字と対応している
・T の i 番目の文字は S に含まれるただ1つの文字と対応している

S,T の全ての文字がこの2つの条件を満たすなら Yes を出力し、満たさないなら No を出力します。この処理は Map を用いることで簡単に書くことができます。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {

		String s = sc.next(), t = sc.next();
		HashMap<Character, Character> S = new HashMap<>();
		HashMap<Character, Character> T = new HashMap<>();
		
		for (int i=0; i<s.length(); i++) {
			
			char a = s.charAt(i);
			char b = t.charAt(i);
			
			if (S.containsKey(a)) {
				if (S.get(a) != b) {
					System.out.println("No");
					return;
				}
			}
			else {
				S.put(a, b);
			}
			
			if (T.containsKey(b)) {
				if (T.get(b) != a) {
					System.out.println("No");
					return;
				}
			}
			else {
				T.put(b, a);
			}
			
		}
		
		System.out.println("Yes");
		
	}
}

S の i 番目の文字を a とします。T の i 番目の文字を b とします。Map S には S(a, b) と格納し、a に対応するものが b だけかどうかを調べます。同様に Map T には T(b, a) と格納し、b に対応するものが a だけかどうかを調べます。

このようにして S,T を最後まで調べていって、全ての文字が条件を満たすなら Yes、1つでも満たさないなら No を出力します。