🎃

Pythonでアナグラム判定

に公開
Python
tech

アナグラム（anagram）とは、文字の順序を入れ替えて別の単語を作ることです。例えば「listen」と「silent」や、「Tom Marvolo Riddle」（トム・マールヴォロ・リドル）と「I am Lord Voldemort」（我輩はヴォルデモート卿なり）はアナグラムの関係にあります。

問題の定義

問題: 2つの文字列 s と t が与えられたとき、それらがアナグラムかどうかを判定する関数を実装してください。

例:

isAnagram("anagram", "nagaram")  # True
isAnagram("rat", "car")          # False
isAnagram("listen", "silent")    # True

アプローチ1: 辞書を使った頻度カウント

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        sdic = {}
        tdic = {}

        for x, y in zip(s, t):
            sdic[x] = sdic.get(x, 0) + 1
            tdic[y] = tdic.get(y, 0) + 1
        
        return sdic == tdic  # 直接返す

コードの解説

1. 長さチェック（早期リターン）

if len(s) != len(t):
    return False

アナグラムは同じ文字数でなければならないので、長さが異なれば即座にFalseを返します。

2. zip()を使った同時処理

for x, y in zip(s, t):
    sdic[x] = sdic.get(x, 0) + 1
    tdic[y] = tdic.get(y, 0) + 1
  • zip(s, t): 2つの文字列を同時にイテレート
  • get(x, 0): キーが存在しない場合は0を返す（KeyErrorを回避）
  • 各文字の出現回数をカウント

計算量

  • 時間計算量: O(n) - nは文字列の長さ
  • 空間計算量: O(k) - kはユニークな文字の数

アプローチ2: Counterを使った実装

collections.Counterを使うと、より簡潔に書けます。

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

メリット

  • 簡潔: 1行で実装できる
  • 可読性: 意図が明確
  • Pythonic: Pythonらしいコード

計算量

  • 時間計算量: O(n)
  • 空間計算量: O(k)

元のコードと同じ計算量ですが、コードがはるかにシンプルです。

長さチェックの最適化

長さが異なる場合の早期リターンを追加すると、わずかに高速化できます。

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return Counter(s) == Counter(t)

アプローチ3: ソートを使った実装

最もシンプルな方法は、文字列をソートして比較することです。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

動作の仕組み

s = "anagram"
t = "nagaram"

print(sorted(s))  # ['a', 'a', 'a', 'g', 'm', 'n', 'r']
print(sorted(t))  # ['a', 'a', 'a', 'g', 'm', 'n', 'r']

# 同じリストなので True

メリット

  • 超簡潔: 1行で完結
  • 直感的: 誰が見ても理解しやすい

デメリット

  • 計算量: O(n log n) - ソートが必要

計算量

  • 時間計算量: O(n log n) - ソートのコスト
  • 空間計算量: O(n) - ソート済みリストを作成

パフォーマンス比較

実際に各アプローチの実行速度を測定してみましょう。

import timeit
from collections import Counter, defaultdict

s = "anagram" * 1000  # 長い文字列でテスト
t = "nagaram" * 1000

# アプローチ1: 辞書
def approach1():
    if len(s) != len(t):
        return False
    sdic, tdic = {}, {}
    for x, y in zip(s, t):
        sdic[x] = sdic.get(x, 0) + 1
        tdic[y] = tdic.get(y, 0) + 1
    return sdic == tdic

# アプローチ2: Counter
def approach2():
    return Counter(s) == Counter(t)

# アプローチ3: ソート
def approach3():
    return sorted(s) == sorted(t)

# 実行時間を測定
print(f"辞書:     {timeit.timeit(approach1, number=1000):.4f}秒")
print(f"Counter:  {timeit.timeit(approach2, number=1000):.4f}秒")
print(f"ソート:   {timeit.timeit(approach3, number=1000):.4f}秒")

典型的な結果:

辞書:     0.8234秒
Counter:  0.7891秒
ソート:   1.2456秒

Counterが最も高速で、ソートは最も遅いことがわかります。

各アプローチの比較表

アプローチ 時間計算量 空間計算量 コード長
辞書（元のコード） O(n) O(k) 中
Counter O(n) O(k) 短い
ソート O(n log n) O(n) 最短

参考

Discussion