771. Jewels and Stones

771. Jewels and Stones

  Solution 01:

 Complexity: O(N^2)

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int cnt = 0;
  for(int i = 0; i < S.size(); i++){
    for(int k = 0; k < J.size(); k++){
        if(S[i] == J[k])cnt++;
    }
    }
        return cnt;
    }
};

Solution 02:

complexity: N log(N)

class Solution {
public:
    int numJewelsInStones(string J, string S) {
   int cnt = 0;

unordered_set<char>jewels;

for(int i = 0; i < J.size(); i++){
    jewels.insert(J[i]);
  }

for(int i = 0; i < S.size(); i++){
    if(jewels.find(S[i]) != jewels.end()) cnt++;
}
return cnt;
    }
};

Solution 03:

Complexity: O(N)

class Solution {
public:
    int numJewelsInStones(string J, string S) {
   int cnt = 0;
        map<char, bool>jewels;

for(int i = 0; i < J.size(); i++){
    jewels[J[i]] = true;
  }

for(int i = 0; i < S.size(); i++){
    if(jewels[S[i]]) cnt++;
}
return cnt;
    }
};

Share: