leetcode讲解--771. Jewels and Stones
文章目录
771. Jewels and Stones
You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in 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:
-
SandJwill consist of letters and have length at most 50. - The characters in
Jare distinct.
看到这个题目首先想到的是要避免过多的循环,这是一个典型的查找类型的题。
最简单最直觉的算法是,每次从J中取出一个字符,然后遍历一遍S,如果找到,就对返回结果+1
但这样的算法复杂度是:O(m*n)
我们可以把J当做一个字典,然后遍历S,看看其中的字符是否在字典内。这样就只需要遍历一遍了。
Java代码
class Solution {
public int numJewelsInStones(String J, String S) {
int result=0;
Map<Character, Integer> JMap = new HashMap<>();
for(Character c:J.toCharArray()){
JMap.put(c, 0);
}
for(Character c:S.toCharArray()){
Integer count = JMap.get(c);
if(count!=null){
result++;
}
}
return result;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论