Valid Anagram
2つの文字列がアナグラムであるとは、一方の文字を並べ替えるともう一方になることです。つまり、同じ文字をそれぞれ同じ回数使っています。小文字の英字で構成された2つの文字列 s と t が与えられます。t が s のアナグラムなら true を、そうでなければ false を返してください。
関数
- sstring
- 最初の文字列、小文字
- tstring
- s と照合する文字列
- 戻り値boolean
- true は、t が s の文字をそれぞれ同じ回数だけ正確に使っている場合
制約
1 ≤ s.length, t.length ≤ 2 × 104sとtには、小文字の英字（aからz）のみが含まれています。- 2つの長さは異なる場合があります。
例
- 入力
- s = "listen"t = "silent"
- 出力
- true
- 説明
- どちらの単語にも
e、i、l、n、s、tが1つずつ含まれているので、silentは文字の順番を入れ替えたlistenです。
- 入力
- s = "aabb"t = "abbb"
- 出力
- false
- 説明
- 長さは一致し、どちらも
aとbだけを使っていますが、aabbにはaが2つあり、abbbには1つあります。文字だけでなく、個数も一致していなければなりません。
- 入力
- s = "cat"t = "cast"
- 出力
- false
- 説明
castは4文字で、catは3文字なので、catを並べ替えてもそれを綴ることはできません。
提出時に隠しテスト+19件
発展問題
文字列が a から z までの文字だけでなく、あらゆる Unicode 文字を格納できるとしたらどうでしょうか？数え方をどのように変えますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
アナグラムでは、文字の順序を無視します。順序は忘れても、各文字が何回現れるかは保持するものとして、何を比較できるでしょうか？
文字を1つずつ並べ替えると、2つのアナグラムは同じ文字列になります。さらに速い方法があります。アルファベットは26文字しかないので、それぞれの文字が何回出現するかを数えればよいのです。
長さが異なる場合、答えは
falseです。それ以外の場合は、26個のカウンターを用意します。sの文字ごとに1を加算し、tの文字ごとに1を減算します。カウンターが一度も0未満にならない場合に限り、文字列はアナグラムです。
解説
アナグラムでは文字の数はそのままに、並び順を無視します。つまり、各文字がどこにあったかは忘れても、それぞれの文字がいくつあるかは覚えている、各文字列の要約が必要です。ソートではその要約を O(n log n) で作成できますが、26個のカウンターを持つテーブルなら1回の走査で作成できます。
両方の文字列を並べ替える
考え方
ソートすると、文字列の文字がアルファベット順に並び、それぞれの文字が元々どこにあったかは分からなくなります。listenをソートするとeilnstになり、silentも同じ結果になるため、これらはアナグラムです。aabbはaabbのまま、abbbはabbbのままです。インデックス1で異なるため、これらはアナグラムではありません。
この判定は両方向で成り立ちます。tがsの文字を並べ替えたものなら、2つの文字列は同じ文字を同じ回数だけ含むため、ソートすると同じ並びになります。ソート後の並びが等しければ、tはsとまったく同じ文字を使っています。
まず長さを比較します。長さの異なる文字列がアナグラムになることはないため、どちらもソートせずに済みます。ソートにはO(n log n)時間がかかり、ほとんどの言語では文字のコピーをソートするため、追加の空間計算量はO(n)です。n = 2 × 10^4の場合、これは高速ですが、文字を数える方法なら処理量をさらに減らせます。
アルゴリズム
sとtの長さが異なる場合は、falseを返します。- 各文字列の文字を配列にコピーします。
- 両方の配列をソートします。
- ソートした配列の要素が1つずつ等しい場合は、
trueを返します。
def isAnagram(s, t):
if len(s) != len(t):
return False
return sorted(s) == sorted(t)各文字を数える
考え方
使われる文字は26文字だけなので、26個の要素を持つ配列に各文字のカウンターを1つずつ用意し、インデックス0をa、インデックス25をzに対応させます。文字のインデックスは、その文字コードからaのコードを引いた値です。sを順に見て各文字のカウンターに1を加え、次にtを順に見て1を引きます。
途中で処理を止めることもできます。カウンターが0未満なら、tに含まれるその文字の数がsより多いことを意味します。aabbとabbbの場合、sを処理した後のカウンターは、aが2、bが2です。次にtでbが3回使われ、3回目でbが-1になるため、その場でfalseを返します。
「カウンターが負にならなかった」だけで十分なのはなぜでしょうか？文字列の長さは等しいので、両方を処理した後のカウンターの合計は0になります。どのカウンターも負でなければ、正の値を相殺するものがないため、すべてのカウンターが0となり、文字数が一致します。だからこそ、長さのチェックは単なる近道ではなく、必要なのです。
各文字列は一度ずつ読み取るため、時間計算量はO(n)です。配列に格納されるのは文字列の長さにかかわらず常に26個の数値なので、追加の空間計算量はO(1)です。
アルゴリズム
sとtの長さが異なる場合は、falseを返します。- 26 個のゼロからなる配列を作成します。
sの各文字について、対応するカウンターに 1 を加えます。tの各文字について、対応するカウンターから 1 を引きます。カウンターが 0 未満になった場合は、falseを返します。trueを返します。
def isAnagram(s, t):
if len(s) != len(t):
return False
counts = [0] * 26 # counts[0] is 'a', counts[25] is 'z'
for ch in s:
counts[ord(ch) - ord("a")] += 1
for ch in t:
index = ord(ch) - ord("a")
counts[index] -= 1
if counts[index] < 0:
return False # t uses this letter more often than s
return True
落とし穴と境界ケース
誤答の多くは、文字の出現回数ではなくどの文字が現れるかを確認したり、長さのチェックを省略したりすることが原因です。
- 文字の集合を比較する。
aabbとabbbはどちらもaとbだけを使っていますが、アナグラムではありません。 tの各文字がsのどこかにあることを、見つけた文字を消し込まずに確認する。aabとabbは、どちらの方向でもこのテストに合格します。- カウント方式で長さのチェックを省略する。
s = ab、t = aの場合、カウンターが0未満にならないため、コードは誤ってtrueを返します。 - カウンター配列のインデックスに文字コードをそのまま使う。
aは97なので、要素数26の配列の範囲を大きく超えます。まずaのコードを引いてください。LuaとRでは配列のインデックスが1から始まるため、1を加えます。
よくある質問4
Valid Anagram の時間計算量はどのくらいですか？
文字数のカウントにかかる時間は O(n)、追加の空間は O(1) です。これは、文字列の長さにかかわらずカウンター配列の要素数が26だからです。両方の文字列をソートするには O(n log n) の時間がかかり、通常、ソート済みのコピーのために O(n) の空間が必要です。
アナグラムかどうかを確認するには、ソートするのと数えるのとでは、どちらがよいでしょうか？
理論上、数え上げの方が高速です。O(n log n)に対してO(n)で、どれか1つの文字が使われすぎた時点で処理を止めることもできます。ソートはより短く書け、変更なしでどのようなアルファベットにも対応します。面接では、まずソートの方法を説明し、その後、数え上げを使う方法に改善しましょう。
Unicode 文字を含むアナグラムはどのように確認しますか？
26個のカウンターの配列を、文字から個数へのハッシュマップに置き換えます。sの各文字について1を加算し、tの各文字について1を減算して、すべてのカウントが最終的に0になることを確認します。文字列はバイト単位ではなく文字単位で読み取り、複数バイトで格納される文字も1文字として数えます。
カウンター配列を2つではなく1つ使うのはなぜですか？
文字列ごとに1つずつ、2つの配列を使う方法でも機能します。それぞれの文字列を数えてから、配列を比較します。sに対して増加し、tに対して減少する1つの配列を使えば、メモリ使用量を半分に抑えられ、カウンターが負になった時点で、最後の比較ループを行わずにfalseを返せます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isAnagram(s, t):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "listen" t = "silent"
期待値
true