771 Jewels and Stones

Easy

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.

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。

示例 1:

1
2

输入: J = "aA", S = "aAAbbbb"
输出: 3

示例 2:

1
2

输入: J = "z", S = "ZZ"
输出: 0

注意:

• S 和 J 最多含有50个字母。
• J 中的字符不重复。

想法

第一感觉是两重循环，遍历S的每一个字符，寻找J里面有没有相同的字符，复杂度是$O(n^2)$。后来想了一下，不需要这么高的复杂度，只需要用一个bool数组把字符是否出现存下来就行。复杂度降至$O(n)$。

解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <cstring>
#include <iostream>

using namespace std;

int numJewelsInStones(string J, string S)
{
    if (J.length() == 0 || S.length() == 0) {
        return 0;
    }
    int ptr[52];
    int temp = 0;
    int res = 0;
    memset(ptr, 0, sizeof(int) * 52);
    for (char &c : J) {
        temp = int(c);
        if (temp > 96) {
            ptr[temp - 71] = 1;
        }
        else {
            ptr[temp - 65] = 1;
        }
    }
    for (char &c : S) {
        temp = int(c);
        if (temp > 96) {
            if (ptr[temp - 71] == 1) {
                res += 1;
            }
        } 
        else if(ptr[temp - 65] == 1) {
            res += 1;
        }
    }
    return res;
}

int main(void)
{
    cout << numJewelsInStones("aA", "aAAbbbb") << endl;
    cout << endl;
}