Isomorphic Strings
2つの文字列は、1つ目の文字列の文字を置き換えて2つ目の文字列にできるとき、同型です。ある文字の出現箇所はすべて同じ新しい文字に置き換えられ、異なる文字が同じ文字に置き換えられることはありません。また、文字をそのままにしてもかまいません。同じ長さの2つの文字列 s と t が同型の場合は true を、そうでない場合は false を返してください。
関数
- sstring
- 名前を変更する文字列、英字と数字
- tstring
- sと同じ長さの、到達する文字列
- 戻り値boolean
- s の文字を一対一で置き換えると t になる場合は true
制約
1 ≤ s.length ≤ 2 × 104t.length == s.lengthsとtには、英字と数字のみが含まれます。大文字と小文字は異なる文字です。
例
- 入力
- s = "noon"t = "deed"
- 出力
- true
- 説明
nをdに、oをeに名前変更します。すべての位置でこの名前変更が適用され、2つの文字には異なる名前が付けられます。
- 入力
- s = "moon"t = "deed"
- 出力
- false
- 説明
- 左から右へ、
mはdに、oはeになり、その後nもdにならなければなりません。異なる2つの文字に同じ名前を付けることはできないので、答えはfalseです。
- 入力
- s = "r2d2"t = "c3p3"
- 出力
- true
- 説明
rはcに、2は3に、dはpになります。数字も文字であり、どちらの2も3になります。
発展問題
単語のリストが与えられたとき、すべての単語のペアを比較せずに、互いに同型な単語をまとめることができますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
sの文字を、左から右へ1つずつ順に置き換えます。先に行った置き換えが邪魔になるのはどんなときですか？sの各文字がtのどの文字になったかを記録します。この記録では、sの異なる2つの文字がtの同じ文字になるという間違いを見逃します。tからsへの2つ目の記録を作れば、この間違いを検出できます。2つのマップを使って、両方の文字列を同時にたどります。
s[i]もt[i]もまだマッピングされていなければ、互いにマッピングします。そうでなければ、すでに互いを指している必要があります。そうでない場合はfalseを返します。
解説
名前の置き換えは双方向で成り立つ必要があります。s の各文字は t の1文字に変換され、t の各文字は s の1文字から変換されます。方向ごとに1つずつ、2つのマップを使って、1回の走査で両方を確認します。
位置のすべてのペアを比較する
正しいが、最大のテストでは終わらない
考え方
名前の付け替えでは、同じ文字は同じ文字のまま、異なる文字は異なる文字のまま保たれます。したがって、位置 i と j のすべての組について、s[i] == s[j] と t[i] == t[j] は同じ結果にならなければなりません。これで十分でもあります。すべての組で一致するなら、s の各文字を、その位置にある t の文字に置き換えることは矛盾なく定義でき、2つの文字に同じ名前を付けることもありません。moon と deed では、位置 0 と 3 の s の文字は異なりますが、t ではどちらも d なので、答えは false です。
組の数はおよそ n²/2 です。n = 2 × 10^4 のとき、どの組でもループが早期終了しない場合は、2 × 10^8 回の比較が必要になります。
アルゴリズム
- すべてのインデックス
iをループし、それぞれについて、それより後のすべてのインデックスjをループします。 s[i]とs[j]が等しいか、またt[i]とt[j]が等しいかを確認します。- 2つの答えが異なる場合は、
falseを返します。 - 最後のペアを確認した後、
trueを返します。
def isIsomorphic(s, t):
n = len(s)
for i in range(n):
for j in range(i + 1, n):
# Two positions must hold equal characters in s exactly when they do in t
if (s[i] == s[j]) != (t[i] == t[j]):
return False
return True各方向に1つずつ、2つのマップ
考え方
読み進めながら対応関係を作ります。sToTにはsの各文字が何に変換されたかを記録し、tToSにはtの各文字がどこから来たかを記録します。位置iでa = s[i]、b = t[i]とすると、両方が新しい文字なら対応付け、そうでなければ、すでに互いを指している必要があります。
対応表は1つだけでは不十分です。sToTだけを使うと、moonとdeedは通過します。これは、sの文字が複数の文字に変換されることがないためです。問題は、mとnの両方がdに変換されることで、位置3ではtToSにすでにdはmに由来すると記録されています。
各位置で必要なのは少数の対応表操作なので、時間計算量はO(n)です。各文字コードは128未満なので、それぞれの対応表を128要素の配列にできます。空間計算量はO(1)です。R版とSwift版では、まず文字列をコード配列にコピーするため、O(n)かかります。
アルゴリズム
- 空のマップを2つ作成します。
sToTとtToSです。 - 各インデックス
iについて、a = s[i]、b = t[i]とします。 aがsToTに存在せず、bがtToSに存在しない場合は、aをbに、bをaに対応付けます。- それ以外の場合、
sToT[a]がbでない、またはtToS[b]がaでないなら、falseを返します。 - 最後のインデックスの後に、
trueを返します。
def isIsomorphic(s, t):
s_to_t = {} # the character of t that each character of s became
t_to_s = {} # the character of s that each character of t came from
for a, b in zip(s, t):
if a not in s_to_t and b not in t_to_s:
s_to_t[a] = b
t_to_s[b] = a
elif s_to_t.get(a) != b or t_to_s.get(b) != a:
return False # a already has another target, or b another source
return True
落とし穴と境界ケース
sからtへの対応表を1つだけ使うこと。これではmoonとdeed、およびabとaaを受け入れてしまいます。- 各文字の出現回数を比較すること。
abcabcとxyzxzyはいずれも3種類の文字をそれぞれ2回使っていますが、2つ目のbは、1つ目のbがyに対応していたのに対し、zに対応しています。 - 大文字と小文字を同じものとして扱うこと。
aAには異なる文字が2つ含まれているため、bbにはなれません。 - 配列マップのサイズを
aからzまでに限定すること。大文字と数字はその範囲外なので、要素数を128にして、文字コード全体を使ってインデックスを指定します。
よくある質問4
Isomorphic Strings の時間計算量はどれくらいですか？
2つのマップを使う解法では各位置を1回ずつ読み取るため、実行時間は O(n) です。マップに格納されるエントリは、英字と数字の計62種類の文字それぞれにつき最大1つなので、追加の領域計算量は O(1) です。すべての位置のペアを比較すると、実行時間は O(n²) かかります。
同型文字列にはなぜ2つのハッシュマップが必要なのですか？
sからtへのマップは、sの1つの文字が2通りの名前に変更されていることを検出します。abとaaのように、sの2つの文字が同じ文字に変更されていることは検出できません。tからsへのマップが、そのケースを検出します。
同型性は対称的ですか？
はい。一対一の名前変更は元に戻せるため、s が t に名前変更されるなら、すべての名前を逆にすることで t は s に戻ります。isIsomorphic(s, t) と isIsomorphic(t, s) の結果は常に一致します。
2つの文字列が同型かどうかを確認する方法はほかにありますか？
各文字を、その文字が最初に現れる位置に置き換えて、結果を比較します。noon と deed はどちらも 0 1 1 0 になり、moon は 0 1 1 3 になります。時間計算量は O(n) で、2つのパターンのために O(n) のメモリを使用します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isIsomorphic(s, t):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "noon" t = "deed"
期待される出力
true