一、题目
LeetCode-771. 宝石与石头
地址：https://leetcode-cn.com/problems/jewels-and-stones/
难度：简单
给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
示例 1:
输入: J = "aA", S = "aAAbbbb"
输出: 3
示例 2:
输入: J = "z", S = "ZZ"
输出: 0
注意:
S 和 J 最多含有50个字母。
J 中的字符不重复。
二、解题思路
方法一：
遍历字符串stones，对于stones 中的每个字符，遍历一次字符串jewels，如果与其相同就是宝石。
/**
* @param {string} jewels
* @param {string} stones
* @return {number}
*/
var numJewelsInStones = function(jewels, stones) {
let n = 0;
for(let i = 0;i < stones.length;++i){
for(let j = 0;j < jewels.length;++j){
if(stones[i] == jewels[j]){
++n;
}
}
}
return n;
};
方法二：
使用哈希集合存储jewels中的字符，然后遍历stones，如果其在哈希集合中就是宝石。
/**
* @param {string} jewels
* @param {string} stones
* @return {number}
*/
var numJewelsInStones = function(jewels, stones) {
let n = 0;
const set = new Set(jewels.split(''));
for(let i = 0;i < stones.length;++i){
if(set.has(stones[i])){
++n;
}
}
return n;
};
三、其他语言实现过程
c++
class Solution {
public:
int numJewelsInStones(string jewels, string stones) {
int n = 0;
unordered_set<char> jewelsSet;
int jewelsLength = jewels.length(), stonesLength = stones.length();
for (int i = 0; i < jewelsLength; i++) {
jewelsSet.insert(jewels[i]);
}
for (int i = 0; i < stonesLength; i++) {
n += jewelsSet.count(stones[i]);
}
return n;
}
};
PHP
class Solution {
/**
* @param String $jewels
* @param String $stones
* @return Integer
*/
function numJewelsInStones($jewels, $stones) {
$n = 0;
$jewels = str_split($jewels);
$stones = str_split($stones);
$map = [];
foreach($jewels as $k => $v){
$map[$v] = $k;
}
$len = count($stones);
for($i = 0;$i < $len;++$i){
if($map[$stones[$i]]){
++$n;
}
}
return $n;
}
}
四、小结
再次遇到用哈希集合解决的题目，对哈希集合也有了一定了解。与算法入门-1. 两数之和 - 简书 (jianshu.com)相似，哈希集合的使用使得两层循环分开进行，算法时间复杂度从O(mn)降到了O(m+n)。
