Jewels and Stones

easy LeetCode #771
hash-table string

Description

You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels. Letters are case sensitive, so 'a' is considered a different type of stone from 'A'.

Example 1:
Input: jewels = "aA", stones = "aAAbbbb"
Output: 3
Explanation: In stones, 'a' appears 1 time and 'A' appears 2 times. Both are jewels. Total jewels = 1 + 2 = 3.

Example 2:
Input: jewels = "z", stones = "ZZ"
Output: 0
Explanation: 'z' (lowercase) is a jewel, but stones only contains 'Z' (uppercase). Case sensitive, so no match.

Constraints

  • 1 <= jewels.length, stones.length <= 50
  • jewels and stones consist of only English letters
  • All the characters of jewels are unique

Complexity

Show Complexity
  • Time: O(m + n)
  • Space: O(m)

Hints

Show Hints
Pattern
Hash set lookup
Approach
Create a set of jewel characters, then count how many stones are in the set
Complexity
Convert jewels to a set for O(1) lookup per stone

Solutions

Show PY Solution 
def solution(jewels: str, stones: str) -> int:
    m = {}
    for c in jewels:
        m[c] = 0

    for s in stones:
        if s not in m:
            continue
        m[s] += 1

    return sum(m.values())