New Tutorials:   KOTLIN    JAVASCRIPT    SASS/SCSS    PL/SQL  
CLOSE
   LeetCode  Algorithm  Cpp  
   Technology    Programming

LeetCode Solution - Jewels and Stones Problem

         
 MAY 6, 2020   by probeta

This article covers the solution for the Leetcode Jewels and Stones Problem. We will cover the complete code solution in the C++ programming language.

Problem Statement:

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character 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.

Jewels and Stones Problem Solution:

This question is straightforward. We have a string S and we need to count those characters in it that are also present in string J.

Logic:

The naive approach to solve this problem would be to compare each character of string S with each character of string J . It would surely give the correct result, but can we do better?

In cases like these, hash maps come to the rescue. As all the letters in J are distinct, we can keep track of which characters are present in it. Then, we just iterate over the string S, and see if that letter is set in the map. If it is so, we increase the count of our answer.

Finally, we return the total count of such letters as our answer.

C++ Code Solution:

Let's see the solution to this problem,

class Solution {
    public:
    int numJewelsInStones(string j ,string s) {
        int n = j.size(),m=s.size();
        int i,count=0;
        map<char,bool> mp;
        for(i=0;i<n;i++) 
        {
            mp[j[i]] = true;
        }
        for(i=0;i<m;i++)
        {
            if(mp[s[i]])
            count++;
        }
        return count;
    }
};

If you have a better solution or any confusion, do let us know by posting in comments.


RELATED POSTS



Subscribe and receive amazing posts directly in your inbox.