Jewels and Stones

You're given stringsJrepresenting the types of stones that are jewels, andSrepresenting the stones you have. Each character inSis a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters inJare guaranteed distinct, and all characters inJandSare 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.

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;
}

results matching ""

    No results matching ""