Pythonで1つ目の文字列の文字から2つ目の文字列を作成できるか判定する方法

問題の概要

2つの文字列 s と t が与えられたとき、t を s に含まれる文字だけを使って作れるかどうかを判定する問題です。ここで重要なのは、s の各文字は一度しか使えないという点です。

例えば、入力が s = "owleh"、t = "hello" の場合、s の文字を組み合わせることで t が作れるため、出力は True になります。

解決のアプローチ

この問題は「文字の出現回数(頻度)を数える」というシンプルな発想で解けます。手順は以下の通りです。

• s の各文字とその出現回数を記録したマップ(freq)を作成する
• t の先頭から順に各文字を確認する
  • freq[t[i]] が 0 の場合、必要な文字がもう残っていないので False を返す
  • そうでなければ freq[t[i]] を 1 減らして次の文字へ進む
• すべての文字を消費できたら True を返す

実装例(Pythonコード)

from collections import defaultdict

def solve(s, t):
    freq = defaultdict(int)

    # s の各文字の出現回数をカウント
    for i in range(len(s)):
        freq[s[i]] += 1

    # t の各文字が s に十分あるか確認
    for i in range(len(t)):
        if freq[t[i]] == 0:
            return False
        freq[t[i]] -= 1
    return True

s = "owhtlleh"
t = "hello"
print(solve(s, t))

入力

s = "owhtlleh"
t = "hello"

出力

True

よりPythonicな書き方:Counterを使う方法

標準ライブラリの collections.Counter を使うと、同じ処理をもっと簡潔に書くことができます。

from collections import Counter

def solve(s, t):
    return not (Counter(t) - Counter(s))

s = "owhtlleh"
t = "hello"
print(solve(s, t))  # True

Counter(t) - Counter(s) は、「t に必要だが s には足りない文字」だけを残します。結果が空であれば、s の文字だけで t を作れることになります。

計算量

• 時間計算量: O(n + m)(n は s の長さ、m は t の長さ)
• 空間計算量: O(k)(k は出現する異なる文字の種類数)

まとめ

文字の頻度を管理することで、アナグラムのような判定問題を効率よく解くことができます。defaultdict や Counter を活用すれば、コードも短く読みやすくなります。ぜひ実際にコードを動かして挙動を確かめてみてください。