Pythonで文字列内の恐竜の数を数える方法

「animals」という文字列と「dinosaurs」という文字列があるとします。animals の各文字は異なる種類の動物を表し、dinosaurs の一意な文字はそれぞれ異なる恐竜を表しています。このとき、animals 文字列の中に含まれる恐竜の総数を求める必要があります。

例えば、入力が animals = "xyxzxyZ"、dinosaurs = "yZ" の場合、出力は 3 になります。これは、恐竜の種類として y と Z の2種類があり、動物の文字列には y が2つ、Z が1つ含まれているためです。

解決のアプローチ

この問題は、以下の手順で解くことができます。

• 結果を格納する変数 res を 0 で初期化する
• dinosaurs を set（集合）に変換し、重複する文字を除去する
• dinosaurs の各文字 c について、animals 内での出現回数を res に加算する
• 最終的な res を返す

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, animals, dinosaurs):
        res = 0
        dinosaurs = set(dinosaurs)
        for c in dinosaurs:
            res += animals.count(c)
        return res

ob = Solution()
animals = "xyxzxyZ"
dinosaurs = "yZ"
print(ob.solve(animals, dinosaurs))

入力

"xyxzxyZ", "yZ"

出力

3

コードの解説

このソリューションでは、まず set() 関数を使って dinosaurs 文字列を集合に変換することで、重複する文字を排除しています。これにより、同じ恐竜の文字を二重にカウントすることを防いでいます。その後、集合内の各恐竜の文字について str.count() メソッドで animals 内の出現回数を数え、合計値を求めています。

計算量について見てみると、animals の長さを n、dinosaurs の一意な文字数を m とすると、全体の時間計算量は O(n × m) になります。

より効率的な代替案：Counter を使う方法

collections.Counter を利用すると、animals の各文字の出現回数を一度だけ数えておき、そこから恐竜の文字を取り出すだけでよくなるため、処理をより効率化できます。

from collections import Counter

class Solution:
    def solve(self, animals, dinosaurs):
        counter = Counter(animals)
        return sum(counter[c] for c in set(dinosaurs))

ob = Solution()
animals = "xyxzxyZ"
dinosaurs = "yZ"
print(ob.solve(animals, dinosaurs))

この方法でも同じ結果である 3 が出力されます。文字列が長くなる場合や、複数回クエリを行う場合には、Counter を使ったアプローチの方が有利です。