题目大意：给你宝石的类型，再给你一堆石头，返回里面宝石的数量。
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:
SandJwill consist of letters and have length at most 50.- The characters in
Jare distinct.
Solution 1: HashTable
Time complexity: O(|J| + |S|)
Space complexity: O(128) / O(|J|)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // Running time: 9 ms class Solution { public: int numJewelsInStones(string J, string S) { std::vector<int> f(128, 0); int ans = 0; for (const char j : J) f[j] = 1; for (const char s : S) ans += f[s] & 1; return ans; } }; |
C++ v2
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua // Running time: 10 ms class Solution { public: int numJewelsInStones(const string& J, const string& S) { std::set<char> f(J.begin(), J.end()); return std::count_if(S.begin(), S.end(), [&f](const char c) { return f.count(c); }); } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua // Running time: 18 ms class Solution { public int numJewelsInStones(String J, String S) { int[] f = new int[128]; for (final char c : J.toCharArray()) f[c] = 1; int ans = 0; for (final char c : S.toCharArray()) ans += f[c]; return ans; } } |
Python
|
1 2 3 4 5 6 7 8 |
""" Author: Huahua Running time: 43 ms """ class Solution(object): def numJewelsInStones(self, J, S): f = set(J) return sum([s in f for s in S]) |