アナグラム判定
listen と silent が同じ、と機械に言わせる
listen と silent、evil と vile。人間は並べ替えれば同じだと一目で分かります。これを判定させるとき、まず浮かぶのは「両方を並べ替えて、一致するか見る」というやり方でしょう。
これは正しく動きます。ただし並べ替えには手間がかかります。文字数を n とすると、実用的な並べ替えでも O(n log n)。長い文字列を大量に突き合わせる場面では、この対数ぶんが効いてきます。
そして、そもそも並べ替える必要があるのか、という疑問が残ります。知りたいのは並び順ではなく、どの文字が何個あるか だけのはずです。
並べ替えなくても、数が合っていればよい
レシートと買い物袋の中身を照合する場面を思い浮かべてください。袋から品物を出す順番はどうでもよく、レシートに書かれた個数と袋の中の個数が一致していればいい。文字も同じです。
数え方も工夫できます。片方を +1、もう片方を -1 として同じ帳簿に付ければ、最後にすべてが 0 なら一致です。表を 2 つ作って突き合わせる必要はありません。
Python
diff = 0
diff += 1 # 片方に 1 個あった
diff -= 1 # もう片方にも 1 個あった
print(diff) # 0 なら釣り合っている文字ごとにこの帳簿を持てば、1 文字につき 1 回の足し引きで済みます。全体で O(n) になり、並べ替えの log n が消えます。
打ち切れるという利点もあります。ある文字の帳簿がマイナスに転んだ瞬間、それは片方にしか無い文字が出てきたということなので、残りを数える意味がありません。
数える前に落とせるものは、先に落とす
長さが違う 2 つの文字列は、1 文字も数えなくてもアナグラムではありえません。
Python
print(len("listen") == len("silent")) # True
print(len("abc") == len("abcd")) # False長さの取得は一瞬で終わるので、この確認を最初に置くだけで、無駄な集計をまるごと省けます。集合を比べる問題では、この「大きさが違うなら即おしまい」という前置きがたいてい効きます。
a と A は、別の文字
最後に、何を同じとみなすかの取り決めです。
Python
print("a" == "A") # Falseプログラムにとって、大文字と小文字は最初から別の文字です。区別するのか、揃えてから比べるのかは仕様の問題であって、どちらかが正しいわけではありません。決まっていないなら、書き始める前に決めてください。空白や記号を無視するかどうかも同じです。「同じとは何か」を曖昧にしたまま書いた判定は、必ずあとで揉めます。
要件
- boolean を返す関数 isAnagram(a, b)
- map / dict を使い、O(n) で判定する (ソートして比較する O(n log n) は避ける)
- 大文字小文字は区別する。長さが違うなら即 false
入出力例
isAnagram("listen", "silent") → true
isAnagram("evil", "vile") → true
isAnagram("hello", "world") → false
isAnagram("abc", "abcd") → false
isAnagram("aA", "Aa") → true
isAnagram("", "") → true
isAnagram("aabb", "abab") → true
isAnagram("rat", "car") → falseヒント
