Jewels and Stones
Count stones whose type appears among the jewels — hash-set membership.
2 min read
hash-set strings
Problem#
Given jewels (distinct characters) and stones, return the number of characters in stones that are also in jewels. Both inputs are case-sensitive.
Examples#
jewels = "aA", stones = "aAAbbbb"→3.jewels = "z", stones = "ZZ"→0.
Constraints#
1 <= jewels.length, stones.length <= 50.
Hints#
Hint
Set lookup per stone.
Approach#
Put jewel chars in a bitset<128> or unordered_set. Walk stones; increment for each character whose flag is set.
Solution#
class Solution {public: int numJewelsInStones(string jewels, string stones) { bitset<128> isJewel; for (char c : jewels) isJewel.set(static_cast<unsigned char>(c)); int ans = 0; for (char c : stones) if (isJewel[static_cast<unsigned char>(c)]) ++ans; return ans; }};func numJewelsInStones(jewels string, stones string) int { isJewel := make(map[byte]bool) for i := 0; i < len(jewels); i++ { isJewel[jewels[i]] = true } ans := 0 for i := 0; i < len(stones); i++ { if isJewel[stones[i]] { ans++ } } return ans}class Solution: def numJewelsInStones(self, jewels: str, stones: str) -> int: jewel_set = set(jewels) return sum(1 for c in stones if c in jewel_set)function numJewelsInStones(jewels, stones) { const jewelSet = new Set(jewels); let ans = 0; for (const c of stones) if (jewelSet.has(c)) ans++; return ans;}class Solution { public int numJewelsInStones(String jewels, String stones) { Set<Character> isJewel = new HashSet<>(); for (char c : jewels.toCharArray()) isJewel.add(c); int ans = 0; for (char c : stones.toCharArray()) { if (isJewel.contains(c)) ans++; } return ans; }}function numJewelsInStones(jewels: string, stones: string): number { const jewelSet: Set<string> = new Set(jewels); let ans = 0; for (const c of stones) if (jewelSet.has(c)) ans++; return ans;}Editorial#
bitset<128> is faster than unordered_set for ASCII because lookups are bit ops. The pattern generalizes: any “membership in small fixed alphabet” can be implemented with a bitset.
Complexity#
- Time: O(N + M).
- Space: O(1).
Concept revision#
Related#