アナグラム判定

listen と silent を比べる

listen と silent、evil と vile は、文字の順を変えると同じ並びになります。このような関係をアナグラムと呼びます。両方を並べ替えて比べる方法でも判定できますが、ここでは何を一致させればよいかを考えます。

文字数をnとすると、一般的な比較による並べ替えは O(n log n) です。長い文字列を大量に照合する場面では、順序を整える処理にも時間がかかります。知りたいのは並び順ではなく、どの文字が何個あるかです。

レシートと袋の個数を照合する

レシートと買い物袋を比べるとき、品物を取り出す順番は問いません。品目ごとの個数が一致すれば、中身は合っています。文字も同じです。集合で文字の種類だけを比べると、同じ文字が何回出たかを見落とします。

片方の文字をすべて数えてから、もう片方の文字を1つずつ引けば、文字ごとの差が求まります。辞書のキーを文字、値を個数の差にします。

counts = {}
counts["a"] = counts.get("a", 0) + 1
counts["a"] = counts.get("a", 0) - 1
print(counts["a"])   # 0

get はキーがなければ指定した0を返します。文字ごとにこの加算と減算を行い、最後にすべての値が0なら同じ個数です。全文字の差をまとめて足すだけでは、ある文字の余りと別の文字の不足が打ち消し合うため判定できません。

先に片方をすべて加算したあとなら、減算中に値が負になった時点で不一致です。もう片方に、その文字が多すぎるからです。2つの文字列を交互に数える方法では、一時的な負の値が出ても、あとで加算して0へ戻る可能性があります。

文字を数える前の取り決め

長さが違えば、並べ替えて同じにはなりません。この回では空白も1文字として数え、大文字と小文字も区別します。a と A は別なので、表でも別のキーになります。空白を無視したり小文字へそろえたりする場合は、そろえたあとの文字列で長さと個数を比べます。

例題で確かめる

3文字の aab と abb を比べます。長さも文字の種類も同じですが、個数まで一致するでしょうか。

差が0でない文字があるので、アナグラムではありません。差の合計は 1 + (−1) = 0 でも、文字ごとの過不足は残ります。aab に必要な2つ目の a は、abb の b で置き換えられません。