这是一道字符的匹配问题,主要的思路就是两个数组各自遍历一边,使用一个unordered_map来记录第一个遍历的数组的信息,遍历第二个数组的时候统计最终的结果。
时间复杂度为O(m + n)。
空间复杂度为O(n)
class Solution { public: int numJewelsInStones(string J, string S) { std::unordered_map<int, int> stones; for(int i = 0; i < S.size(); ++i){ if(stones.count(S[i]) == 0){ stones[S[i]] = 1; } else { ++stones[S[i]]; } } int jewel_cnt = 0; for(int i = 0; i < J.size(); ++i){ if(stones.count(J[i]) > 0){ jewel_cnt += stones[J[i]]; } } return jewel_cnt; } };