LeetCode "Jewels and Stones": counting certain characters in a string LeetCode "Jewels and Stones"


  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:
  
  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 &lt; J.length(); i++ )
        {
            for( int j = 0; j &lt; 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&lt;Character&gt; jSet = new HashSet&lt;&gt;();
        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))?
Caution — naïve application of big-O analysis will lead you astray here!

First of all, you should be more precise about what you mean by "n".  In this problem, there are |J| and |S|: the lengths of J and S.  Your first approach is O(|J| |S|); your second one is O(|J| + |S|).

More importantly, big-O analysis only tells you how well an algorithm scales to handle large inputs.  In this challenge, though, |J| and |S| are at most 50 — very small inputs, by computer standards.  That means that the constant factors, which are disregarded in big-O analysis, actually matter.  (Another way to look at it: with those limits, |J| and |S| are both O(1), so any sane solution is also O(1)!)

Consider how much code is involved in making a HashSet.  A HashSet is actually a disguise for a HashMap.  A HashMap is implemented as an array of trees, each containing Map.Entry objects.  The array should be optimally sized to hold all the characters of J with no hashcode collisions, but you neglected to specify size hints when calling the HashSet&lt;&gt;() constructor.  Then, you have to insert each character of J, which involves boxing a char into a Character, calculating its hashcode, making a Map.Entry for it, and inserting it into the HashMap's table.  The problem is, Java makes it easy to execute a lot of operations without making you aware of how much work it actually is!

Since the challenge states that all characters are letters — which I interpret to mean the 52 letters in the English alphabet, you could achieve an efficient test of membership in J using a simple lookup table:

public int numJewelsInStones(String j, String s) {
    boolean[] jewels = new boolean[128];
    for (int i = 0; i &lt; j.length(); i++) {
        jewels[j.codePointAt(i)] = true;
    }
    int count = 0;
    for (int i = 0; i &lt; s.length(); i++) {
        if (jewels[s.codePointAt(i)]) {
            count++;
        }
    }
    return count;
}