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: 3Example 2:
Input: J = "z", S = "ZZ"
Output: 0Note:
S and J will consist of letters and have length at most 50. The characters in J are distinct.
My approach:
class Solution {
public int numJewelsInStones(String J, String S) {
int count = 0;
for( int i = 0; i < J.length(); i++ )
{
for( int j = 0; j < S.length(); j++ )
{
if( J.charAt(i) == S.charAt(j) )
count++;
}
}
return count;
}
}
Time complexity: O(n^2)
Space complexity: O(1)
Another approach:
class Solution {
public int numJewelsInStones(String J, String S) {
Set<Character> jSet = new HashSet<>();
for(Character ch : J.toCharArray()) {
jSet.add(ch);
}
int count = 0;
for(Character ch: S.toCharArray()) {
if(jSet.contains(ch)) {
count++;
}
}
return count;
}
}
Time complexity: O(n) Space complexity: O(n)
I have the following questions regarding the above code snippets:
Which approach is better according to you?
Will the interviewer be more impressed by the 2nd method as it has used Set?
How can I further improve my code (sort the string and perform a binary search)-> O(n*log(n))?