[LeetCode]771.Jewels and Stones

771. Jewels and Stones

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:

1
2
Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

1
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.

解释一下题目:

在第二个字符串中,找出在第一个字符串中出现的字符的个数,其中,第一个字符串中的字符是不重复的。

思路:对于是否在第一个字符中出现,可以把第一个字符串的字符当做一个集合,再去判断元素是否在集合中,两个循环即可解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int numJewelsInStones(string J, string S) {
int size = J.length();
set<char> jewel_set;
for (unsigned int i = 0; i < size; ++i) {
jewel_set.insert(J[i]);
}
int count = 0;
size = S.length();
for (unsigned int i = 0; i < size; ++i) {
if (jewel_set.count(S[i])) {
count++;
}
}
return count;
}
};

result

Runtime: 8 ms, faster than 74.17% of C++ online submissions for Jewels and Stones.

Memory Usage: 9.9 MB, less than 54.58% of C++ online submissions for Jewels and Stones.

代码再简洁优化下,使用C++11的for循环,并且增加const限定符,程序快了,内存占用也降低了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int numJewelsInStones(string J, string S) {
int size = J.length();
set<char> jewel_set;
for (const char &ch : J) {
jewel_set.insert(ch);
}
int count = 0;
size = S.length();
for (const char &ch: S) {
if (jewel_set.count(ch)) {
count++;
}
}
return count;
}
};

result

Runtime: 4 ms, faster than 100.00% of C++ online submissions for Jewels and Stones.

Memory Usage: 8.6 MB, less than 98.64% of C++ online submissions for Jewels and Stones.