【Python入門】宝石と石の問題を辞書で解くアルゴリズム解説

問題概要

文字列 J は「宝石」とみなされる文字の集合を表し、もう一方の文字列 S は手元にある「石」を表しています。この課題では、S の中に宝石として扱える石がいくつ含まれているかを求めます。J と S に含まれる文字は大文字・小文字が区別される点に注意してください。

たとえば、J = "aZc"、S = "catTableZebraPicnic" の場合、宝石に該当する文字は 7 個含まれています。

解き方のアプローチ

この問題を効率よく解くには、まず文字列 J を辞書（ハッシュマップ）に変換し、各文字をキーとして登録します。その後、文字列 S を先頭から順に走査し、各文字が辞書に存在するかどうかを確認します。存在していればカウントを 1 ずつ増やしていきます。

辞書を使うことで、文字の存在確認が平均 O(1) で行えるため、全体の計算量は O(|J| + |S|) となり、非常に効率的です。

実装例

以下のコードは、上記のアプローチを実際に実装したものです。

class Solution(object):
    def numJewelsInStones(self, J, S):
        jewels = {}
        for i in J:
            jewels[i] = 1
        number = 0
        for i in S:
            if i in jewels:
                number += 1
        return number

ob1 = Solution()
print(ob1.numJewelsInStones("aZc", "catTableZebraPicnic"))

入力

"aZc"
"catTableZebraPicnic"

出力

7

コードのポイント

• 辞書による高速な検索： 宝石の文字を事前に辞書へ登録しておくことで、S の各文字が宝石かどうかを効率的に判定できます。
• 大文字・小文字の区別： Python の文字列比較はデフォルトで大文字・小文字を区別するため、追加の前処理は不要です。
• より簡潔な書き方： Python では sum(s in J for s in S) のようなジェネレーター式を利用すれば、わずか 1 行で同じ結果を得ることもできます。

まとめ

本記事では、宝石の文字を格納した辞書を活用して、石の中から宝石に該当するものを数える方法を解説しました。計算量 O(|J| + |S|) で処理できるため、文字列が長くなっても高速に動作します。シンプルながら辞書（セットも可）の活用法を学べる、定番のアルゴリズム問題といえるでしょう。