JewelsAndStones [source code]

public class JewelsAndStones {
static
/******************************************************************************/
class Solution {
    public int numJewelsInStones(String J, String S) {
        char[] chs = S.toCharArray ();
        int res = 0;
        for (char c : chs) {
            if (J.indexOf (c) >= 0)
                res++;
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        JewelsAndStones.Solution tester = new JewelsAndStones.Solution();
        String[] inputs = {
            "aA", "aAAbbbb", "3",
            "z", "ZZ", "0",
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            String J = inputs[3 * i], S = inputs[3 * i + 1];
            int ans = Integer.parseInt (inputs[3 * i + 2]);
            System.out.println (Printer.separator ());
            int output = tester.numJewelsInStones (J, S);
            System.out.printf ("%s and %s -> %s, expected: %d\n", 
                J, S, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

contest的时候做的, 速度是19ms (NA);

editorial

Approach #1: Brute Force [Accepted]

Intuition and Algorithm

For each stone, check whether it matches any of the jewels. We can check with a linear scan.

class Solution {  
    public int numJewelsInStones(String J, String S) {  
        int ans = 0;  
        for (char s: S.toCharArray()) // For each stone...  
            for (char j: J.toCharArray()) // For each jewel...  
                if (j == s) {  // If the stone is a jewel...  
                    ans++;  
                    break; // Stop searching whether this stone 's' is a jewel  
                }  
        return ans;  
    }  
}

不如用indexOf算了; 听说速度更快;

Approach #2: Hash Set [Accepted]

Intuition and Algorithm

For each stone, check whether it matches any of the jewels. We can check efficiently with a Hash Set.

class Solution {  
    public int numJewelsInStones(String J, String S) {  
        Set<Character> Jset = new HashSet();  
        for (char j: J.toCharArray())  
            Jset.add(j);  

        int ans = 0;  
        for (char s: S.toCharArray())  
            if (Jset.contains(s))  
                ans++;  
        return ans;  
    }  
}

这个是认为用hash的查询速度更快, 理论上可以做到O(1); 所以这个做法的复杂度实际上是更好的, 做到了linear; 如果面试这个问题, 要知道这个想法, 虽然只是通过提升lookup的速度来完成一个提速, 但是也是一个提速的切入点, 你要想得到;

discussion没有什么特别的办法, submission没有东西;

Problem Description

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.
Difficulty:Easy
Total Accepted:2.4K
Total Submissions:2.7K
Contributor:lokendrajain1994
Companies
amazon
Related Topics
hash table