LeetCode #771 Jewels and Stones

Easy

Problem

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

Convert J to be a set and search all elements of S in this set.

Complexity

Convert J to be a set takes O(n) time, where n denotes all types of jewels. Search stones in this set takes O(m)/O(mlogn) time in average/worst cases, where m denotes to counts of stones. And sum the result up takes O(m) time. Therefore, its time complexity will be O(n + m + m)/O(n + mlogn + m) = O(n + m)/O(n+mlogn) in average/worst cases.

For space complexity, the set uses O(n) extra space.

It’s noted that if you don’t convert J to be a set and search stones in it directly, i.e. line 13 becomes return sum([s in J for s in S]), it will take O(nm) time for searching all stones in jewels with O(1) extra space.