5
\$\begingroup\$

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 < 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:

  1. Which approach is better according to you?

  2. Will the interviewer be more impressed by the 2nd method as it has used Set?

  3. How can I further improve my code (sort the string and perform a binary search)-> O(n*log(n))?

\$\endgroup\$
6
\$\begingroup\$

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<>() 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 < j.length(); i++) {
        jewels[j.codePointAt(i)] = true;
    }
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        if (jewels[s.codePointAt(i)]) {
            count++;
        }
    }
    return count;
}
\$\endgroup\$
4
\$\begingroup\$

Not much time, so just in short:

  1. Definitely the second. It shows that you have got at least a general grip on datastructures (knowing the complexity of HashSet operations) and know a bit about the standard library. Regarding the fist one: this even uses a loop instead of indexOf - I'd immediatly show you to the door for that, if I were the interviewer...
  2. Second is definitely better, but not impressive eiher. Try getting a grip on the stream API and play around with String.codePoints - my own try-that-for-comparison-solution was 2 lines using this...
  3. You shouldn't. From my opinion, it is OK to explain in addition that there might be a possible solution using binary search over the stones string, which completes in \$O(n\times log(n))\$, but I would not to see an even longer solution for micro-optimizing a simple problem which takes milliseconds to execute. Simplicity, readability and clarity are the key attributes.
\$\endgroup\$
  • \$\begingroup\$ Thank you, @mtj for this advice. I had thought that writing extra code for binary search won't be useful enough as it will decrease the overall readability without giving a substantial advantage. I would love to check out String.codePoints. \$\endgroup\$ – Anirudh Thatipelli May 3 '18 at 10:27
3
\$\begingroup\$

You could speed up the first version by switching the loops, so that the loop over J becomes the inner loop, and short-circuiting the loop over J, because once you have found a character in J that matches the current character in S, you don't have to loop over the remaining characters of J (mtj's suggestion to use String.indexOf(char) would amount to this).

As for the second approach: Why do you first convert the strings to a char[] before iterating over their characters? You did not do this in the first version, so what do you gain from it by doing it in the second version?

About your question which approach is better: Depends on what you mean by better. I think both versions are quite straighforward and to the point. For large strings, the second version might be preferable because it has a lower time complexity. However, you write that the strings will contain at most 50 characters, so the benefit of constant-time lookup might not outweigh the cost of creating a Set and implicitly converting each primitive char to a Character object. But this is just a guess, I did not measure it.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your valuable comments, @Stingy. I thought about using binary search and improving my time complexity to O(n*log(n)). What is your take on this? Does sorting create another overhead? \$\endgroup\$ – Anirudh Thatipelli May 3 '18 at 10:25
  • \$\begingroup\$ @AnirudhThatipelli I don't quite understand. I would have thought that \$O(n\cdot\log(n))\$ is worse than \$O(n)\$, since it has an other factor that grows with \$n\$? \$\endgroup\$ – Stingy May 3 '18 at 10:35
  • \$\begingroup\$ I was talking about my first approach. The time complexity is O(n^2) which I can reduce using binary search instead of the inner for loop. But, @mtj's point makes sense here as it would decrease the readability of the code. \$\endgroup\$ – Anirudh Thatipelli May 3 '18 at 10:37
  • \$\begingroup\$ @AnirudhThatipelli Again, time complexity and speed are two different things. Time complexity only means how the growth of the input would affect the speed, but it doesn't say anything about how two algorithms will perform compared to each other on the same input. If you want to know which one is faster, you'll have to measure it. But then, with such small input sizes, I doubt that it matters, and as mtj has pointed out, I think simplicity, readability and clarity are more important here than micro-optimizations. \$\endgroup\$ – Stingy May 3 '18 at 10:47
  • \$\begingroup\$ Oh right. I may have been confusing time complexity with speed!! \$\endgroup\$ – Anirudh Thatipelli May 3 '18 at 10:49
-1
\$\begingroup\$
public long numJewelsInStones(String J, String S) {
    Set<Character> jewels = J.chars().mapToObj(c -> (char) c).collect(Collectors.toSet());
    return jewels.stream().filter(x -> S.contains(x + "")).count();
}

Definitely, second approach is better, java 8 can actually truncate it further. Also jewels is a better name than jSet.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think this is wrong, as it only counts each jewel once? \$\endgroup\$ – Koekje May 3 '18 at 13:41
  • \$\begingroup\$ Thanks, @Tanvi Jaywant. I will try out your approach as well. I have never used mapTo in Java. \$\endgroup\$ – Anirudh Thatipelli May 3 '18 at 15:20
  • \$\begingroup\$ @Koekje letters in J are guaranteed distinct right ? \$\endgroup\$ – Tanvi Jaywant May 3 '18 at 16:22
  • 1
    \$\begingroup\$ @TanviJaywant correct, but take example 1, J = "aA", S = "aAAbbbb", you will stream over each jewel counting 1 for each that is contained in S. This will return 2, when in fact there are 3 jewels between the stones. \$\endgroup\$ – Koekje May 3 '18 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.