Pythonで文字列の文字を入れ替えて別の文字列を作れるか判定する方法

2つの文字列 s と t が与えられたとき、s の文字を入れ替えることで t を作れるかどうかを判定する問題です。これはいわゆる「アナグラム（並べ替え）判定」の一種と言えます。

例えば、入力が s = "worldlloeh"、t = "helloworld" の場合、出力は True になります。"worldlloeh" の文字を適切に入れ替えることで "helloworld" を作れるためです。

解法のアプローチ

この問題は、両方の文字列に含まれる各文字の出現回数を比較することで効率的に解けます。手順は以下の通りです。

• s_len := s の長さ、t_len := t の長さとする
• s_len と t_len が一致しない場合は、False を返す
• freq := s の各文字とその出現回数を記録するマップ（辞書）を作成する
• i を 0 から t_len - 1 まで繰り返す：
  • freq[t[i]] を 1 減らす
  • freq[t[i]] が 0 未満になった場合は False を返す（t に必要な文字が s に足りないことを意味する）
• 最後に True を返す

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

from collections import defaultdict

def solve(s, t):
    s_len = len(s)
    t_len = len(t)
    if (s_len != t_len):
        return False
    freq = defaultdict(int)
    for char in s :
        freq[char] += 1
    for i in range(t_len) :
        freq[t[i]] -= 1
        if freq[t[i]] < 0:
            return False
    return True

s = "worldlloeh"
t = "helloworld"
print(solve(s, t))

入力

"worldlloeh", "helloworld"

出力

True

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です（n は文字列の長さ）。まず文字列の長さが同じであることを確認し、その後、各文字の出現回数を1回ずつ数えるだけで済むため、非常に効率的な方法です。