Leetcode 771 - Jewels and Stones

Problem Statement

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S 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 in J and S 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 2:

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.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def numJewelsInStones(self, J, S):
count = 0
chars = [0] * 255
for c in J:
ascii = ord(c)
chars[ascii] = 1
for c in S:
ascii = ord(c)
if chars[ascii]:
count += 1
return count

Time: O(J + S)

Space: O(1)

Explanation

So there are 255 ascii codes and you are restriced to letters in this problem statement. If J or S could consist of Unicode characters then you should expand that to use a set or a dictionary instead of an array, but then the space complexity would jump to O(J) since now the size of the set or dictionary depends on the characters in J. The takeaway here is that the characters for A-Z are between 65 - 90 and a-z is from 97 - 122. You can create a fixed size array and then index into that array by subtracting a character’s ascii value by 97 or 65.