Jewels and Stones

石を1個ずつ取り出します。それぞれの石について、jewelsを順に調べ、一致する最初の文字で止めます。一致したら、カウントに1を加えます。最初の例では、石uをrおよびRと比較しますが、一致するものがないため、何も加算されません。

宝石の文字はすべて異なるため、石が一致するのは最大でも1つです。そのため、最初に一致した時点で止められます。宝石ではない石は、それが分かるまで、すべての宝石の文字と比較する必要があります。

宝石の種類がj個、石がs個ある場合、比較回数は最大でj × s回です。ここではj ≤ 52なので、石が10^4個でも比較回数は約5 × 10^5回となり、スキャンは時間内に完了します。種類のリストが大きくなると無駄が目立ちます。石ごとに同じ検索を繰り返すからです。

「この文字は宝石か？」という質問は、同じ文字について尋ねるたびに答えが変わりません。そこで種類ごとに一度だけ答えられるよう、jewels の文字から集合を作ります。集合を使うと要素の有無を定数時間で調べられるため、石ごとの処理は走査ではなく1回の検索で済みます。

最初の例では、集合は {r, R} です。rubyRRr を順に調べると、検索結果は「はい、いいえ、いいえ、いいえ、はい、はい、はい」となり、宝石は4個です。集合の作成には j ステップ、走査には s ステップかかるため、合計は O(j + s) です。

集合に格納される文字は最大でも 52 個です。組み込みの集合がない言語では、文字コードを添字にしたフラグ配列で同じ処理ができます。