Formatted question description: https://leetcode.ca/all/771.html

771. Jewels and Stones

Level

Easy

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.

Solution

If either J or S is empty, return 0.

For each letter in S, check whether the letter is in J. If so, the letter represents a jewel, so add the counter by 1. Finally, return the counter.

  • public class Jewels_and_Stones {
    
        public class Solution {
            /**
             * @param J: the types of stones that are jewels
             * @param S: representing the stones you have
             * @return: how many of the stones you have are also jewels
             */
            public int numJewelsInStones(String J, String S) {
                if (J == null || J.length() == 0 || S == null || S.length() == 0) { return 0; }
                // replace all non-from-J characters from S, then compute its' length
                return S.replaceAll("[^" + J + "]", "").length();
            }
        }
    
    
        class Solution_brute_force {
            public int numJewelsInStones(String J, String S) {
                if (J == null || S == null) {
                    return 0;
                }
    
                char[] jArray = J.toCharArray();
                char[] sArray = S.toCharArray();
    
                int count = 0;
                for (char c: sArray) {
                    for (char target: jArray) {
                        if (c == target) {
                            count++;
                            break;
                        }
                    }
                }
    
                return count;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/jewels-and-stones/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int numJewelsInStones(string J, string S) {
            unordered_set<char> s(J.begin(), J.end());
            int ans = 0;
            for (char c : S) ans += s.count(c);
            return ans;
        }
    };
    
  • class Solution(object):
        def numJewelsInStones(self, J, S):
            """
            :type J: str
            :type S: str
            :rtype: int
            """
            return sum(S.count(j) for j in J)
    

Java

  • class Solution {
        public int numJewelsInStones(String J, String S) {
            if (J == null || S == null || J.length() == 0 || S.length() == 0)
                return 0;
            int jewels = 0;
            int length = S.length();
            for (int i = 0; i < length; i++) {
                char c = S.charAt(i);
                int index = J.indexOf(c);
                if (index >= 0)
                    jewels++;
            }
            return jewels;
        }
    }
    
  • // OJ: https://leetcode.com/problems/jewels-and-stones/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int numJewelsInStones(string J, string S) {
            unordered_set<char> s(J.begin(), J.end());
            int ans = 0;
            for (char c : S) ans += s.count(c);
            return ans;
        }
    };
    
  • class Solution(object):
        def numJewelsInStones(self, J, S):
            """
            :type J: str
            :type S: str
            :rtype: int
            """
            return sum(S.count(j) for j in J)
    

All Problems

All Solutions