解答と解説: Isomorphic Strings

「問題演習: Isomorphic Strings」の解答編です。今回の解答例には、比較的すぐに思いつきそうなものと、簡単な制約がある場合に思いつきたい解答を載せました。

解答例

Javaでの解答例です。

解答例１）

	public class Solution {
	public boolean isIsomorphic(String s1, String s2) {
	Map<Character, Character> map = new HashMap<>();
	for (int i = 0; i < s1.length(); i++) {
	char c1 = s1.charAt(i);
	char c2 = s2.charAt(i);
	if (map.containsKey(c1)) {
	if (map.get(c1) != c2) {
	return false;
	}
	} else if (map.containsValue(c2)) {
	return false;
	} else {
	map.put(c1, c2);
	}
	}
	return true;
	}
	}

view raw isomorphic-string.java hosted with ❤ by GitHub

解答例２）

	public class Solution {
	public boolean isIsomorphic(String s1, String s2) {
	char[] a1 = new char[256];
	char[] a2 = new char[256];
	for (int i = 0; i < s1.length(); i++) {
	char c1 = s1.charAt(i);
	char c2 = s2.charAt(i);
	if (a1[c1] == 0 && a2[c2] == 0) {
	a1[c1] = c2;
	a2[c2] = c1;
	} else if (a1[c1] != c2 || a2[c2] != c1) {
	return false;
	}
	}
	return true;
	}
	}

view raw isomorphic-string.java hosted with ❤ by GitHub

解説

この問題は 2 つの文字列に含まれる各文字が 1 対 1 にマッピングできるか否かを調べる問題でした。この問題文からまず思いつくのが、解答例１のようにマップを使った解答です。マップを使って文字列 s1 と s2 で用いられている文字の対応表を作り、１対多もしくは多対１の関係が見つかり次第、調査を終了し false を返しています。

さらっと書きましたが、ここで注意したいことは１対多を調べるだけでなく、多対１も調べなくてはならない点です。例えば 2 つの文字列 "aaaaa" と"abcde" が引数 s1 と s2 として与えられた場合、解答例１では map.containsKey(c1) によって 'a' マップに既に登録されているか調べています。しかしこれだけでは "abcde" と "aaaaa" が引数 s1 と s2 として与えられた場合は重複を発見することができません。そのため map.containsValue(c2) にて 2 つ目の文字列がマップの値として既に登録されていないか調べています。

もし、マップを使うことができないという制約が問題に付け加えられた場合どうしますか。解答例２がそのときの解法になります。解答例２では、長さ 256 の文字配列を 2 つ用意しています。長さを 256 にしているのは、アルファベットや数字を含む ASCII 文字列が 256 文字以内に収まるからです。扱わなくてはならない文字の増減によって、サイズを変える必要があります。

配列には、文字を int 型で表現した整数をインデックスとし、他方の文字列での対応する文字を格納します。つまり、文字列 "abc" と "xyz" が引数 s1 と s2 として与えられた場合、s1 の最初の文字 'a' は int 型で 97 なので、a1[97] = 'x' を格納します。次の 'b' は int 型で 98 なので a[98] = 'y' を格納します。また、配列を 2 つ用意している理由は、上述のように 1 対多だけでなく多対１も調べる必要があるためです。

以上が今回の解説になります。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。