본문 바로가기

알고리즘_개념 및 문제풀이

Leetcode/jewels and stones/해시/Hash

반응형

https://leetcode.com/problems/jewels-and-stones/

 

Jewels and Stones - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

It can be solved using the Hash. Put all S string's char as a key and count integer as a value. ('count integer' is how to calculate the n-times per each char as an integer). ex) "aaa" => hash['a'] = 3  (I have 3 'a's). And then Based on that Hash I made, Loop the J string. while looping, add the value if n'th char in the J string find the pair of key and value. 

int numJewelsInStones(string J, string S) {
        unordered_map<char, int> check;
        int answer = 0;
        for(int i = 0; i < S.size(); i++){ // O(n)
            check[S[i]]+=1;
        }
        for(int j = 0; j < J.size(); j++){ // O(n)
            answer += check[J[j]];
        }
        return answer;
    }

Time Complexity: O(n) 

반응형