Jewels and Stones
You're given stringsJ
representing the types of stones that are jewels, andS
representing the stones you have. Each character inS
is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters inJ
are guaranteed distinct, and all characters inJ
andS
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
andJ
will consist of letters and have length at most 50.The characters in
J
are distinct.
Analysis
Use Hash Table - O(M) space, O(N) time, where M is length of J
, and N is length of S
Solution
Hash Set - O (N) - (15ms 26.72%)
class Solution {
public int numJewelsInStones(String J, String S) {
if (J == null || J.length() == 0 || S == null || S.length() == 0) {
return 0;
}
HashSet<Character> jewels = new HashSet<Character>();
int count = 0;
for (int i = 0; i < J.length(); i++) {
jewels.add(J.charAt(i));
}
for (int i = 0; i < S.length(); i++) {
if (jewels.contains(S.charAt(i))) {
count++;
}
}
return count;
}
}
class Solution {
public int numJewelsInStones(String J, String S) {
HashSet set = new HashSet();
for (int i = 0; i < J.length(); i++) {
set.add(J.substring(i,i+1));
}
int tick = 0;
for (int i = 0; i < S.length(); i++) {
String temp = S.substring(i,i+1);
if (set.contains(temp)) {
tick++;
}
}
return tick;
}
}
For small input, this might be better solution
public static int numJewelsInStones(String J, String S) {
int res=0;
for(char c : S.toCharArray()){
if(J.indexOf(c) != -1){
res++;
}
}
return res;
}
Last updated
Was this helpful?