Jewels and Stones
Question
You're given strings
J
representing the types of stones that are jewels, andS
representing the stones you have. Each character inS
is a type of stone you have. You want to know how many of the stones you have are also jewels.The letters in
J
are guaranteed distinct, and all characters inJ
andS
are letters. Letters are case sensitive, so"a"
is considered a different type of stone from"A"
.
Example 1:
Input: J = "aA", S = "aAAbbbb" Output: 3
Example 1:
Input: J = "z", S = "ZZ" Output: 0
Note:
S and J will consist of letters and have length at most 50. The characters in J are distinct.
Approach 1: Brute Force
Intuition and Algorithm
The brute force approach is simple. Loop through each element i ,j and find if they are equal.
1 | class Solution: |
- Runtime: 40 ms, faster than 68.64% of Python3 online submissions for Jewels and Stones.
- Memory Usage: 13.3 MB, less than 5.25% of Python3 online submissions for Jewels and Stones.
Approach 2: Hash Table
In my opinion, the second approach cancels the nested loop which should be much faster than the first approach. However, it has no effect at all. :worried:
1 | class Solution: |
- Runtime: 40 ms, faster than 68.64% of Python3 online submissions for Jewels and Stones.
- Memory Usage: 13 MB, less than 5.25% of Python3 online submissions for Jewels and Stones.